[Python] 25635번 자유 이용권

 

 

https://www.acmicpc.net/problem/25635

25635번: 자유 이용권

---

 

22/11/18

 

 

전형적인 그리디 문제로, 그리디 문제 특성상 태그를 안 까면 접근할 때 방황할 수 있기 때문에, 이 문제를 어떻게 접근했는지 알아볼 필요가 있다.

---

 

문제 접근 방식:

 

 

연속해서 같은 놀이기구를 탈 수 없다는 조건을 보고, 서로 다른 놀이기구를 교대로 타면 많이 탈 수 있을 것이라고 처음에 막연하게 생각했다.

 

예제 입력 1을 보고, 제일 먼저 타야되는 놀이기구는 이용 횟수가 제일 많이 남은 놀이기구라는 사실을 알게 되었다.

 

이를 통해 맨 처음 떠올렸던 문제 접근 방식은 이용 횟수가 제일 많이 남은 놀이기구를 먼저 타고, 그 놀이기구의 이용 횟수를 줄이고, 그다음으로 이용 횟수가 제일 많이 남은 놀이기구를 타고, 그 놀이기구의 이용 횟수를 줄이고...

 

이런 식으로 직접 시뮬레이션을 하며 푸는 방식을 생각했었다.

 

하지만, 문제에서 주어진 $N$의 범위가 $100,000$까지였기 때문에, 그렇게 시뮬레이션을 하면 시간 초과가 날 뿐더러, 종료 조건 또한 어떻게 해야 할지 명확하게 나오지 않아서 시뮬레이션으로 접근하는 방식은 조금 잘못된 방식이라고 생각했었다.

 

때문에 새로운 접근 방식을 떠올릴 필요가 있었다.

 

 

나는 "이용 횟수가 제일 많이 남은 놀이기구를 먼저 타야만 된다는 사실"에 주목했다.

 

이용 횟수가 제일 많이 남은 놀이기구를 구하기 위해서는 "정렬"을 해야만 하는데, "정렬"문제는 그리디 알고리즘과 엮여져 나오는 경우가 많이 때문에 그리디적인 접근으로 풀어야겠다는 생각을 했다.

 

또한, 예제 입력 2와 예제 입력 3을 직접 시뮬레이션 해보며 굳이 직접 시뮬레이션을 하지 않아도 된다는 사실을 알았다.

 

 

예제 입력 1과 예제 입력 2, 예제 입력 3을 직접 시뮬레이션 해가며 나온 결과를 한 번 살펴보자.

예제 입력 1	예제 입력 2	예제 입력 3
1, 1, 3  -> 0 1, 1, 2  -> 1 1, 0, 1  -> 2 1, 0, 0  -> 3 0, 0, 0  -> 4	3, 5  -> 0 3, 4  -> 1 2, 4  -> 2 2, 3  -> 3 1, 3  -> 4 1, 2  -> 5 0, 2  -> 6 0, 1  -> 7	2, 2, 2, 3  -> 0 2, 2, 2, 2  -> 1 2, 2, 1, 2  -> 2 2, 2, 1, 1  -> 3 2, 1, 1, 1  -> 4 1, 1, 1, 1  -> 5 ...

이렇듯, 제일 많이 이용횟수가 남아있는 놀이기구(이를 $MAX$라고 부르자)를 중심으로 교대로 타다 보면 최대의 결과를 얻어낼 수 있다는 사실을 알아낼 수 있다.

 

특히, 예제 입력 3을 한번 주목해보자.

 

예제 입력 3을 보면, $MAX$의 이용 가능 횟수는 3회이고, 그 이외의 놀이기구의 이용 가능 횟수는 2회, 2회, 2회로, 총 6회이다.

 

따라서 $MAX$의 이용 횟수보다, 그 이외의 놀이기구들의 이용 가능 횟수의 합(이를 $OTHER \ SUM$이라고 하자)이 더 많은 경우, 예제 입력 3처럼 적절하게 분배하여 $MAX$의 이용 횟수를 모두 소진시키게 만들 수 있다.

 

따라서 이 경우에서는 모든 놀이 기구의 이용 횟수를 모두 소진시킬 수 있다.

 

 

만약 같은 경우라면 어떻게 될까?

 

예를 들어, 2, 2, 4처럼 주어진다면 다음과 같이 분배할 수 있을 것이다.

 

4개짜리 타기 -> 2개짜리 타기 -> 4개짜리 타기 -> 2개짜리 타기 -> 4개짜리 타기 -> 2개짜리 타기 -> 4개짜리 타기 -> 2개짜리 타기

이렇듯 적절하게 분배하여 모든 이용횟수를 소진시킬 수 있다.

 

 

만약 $MAX$의 이용 횟수가 $OTHER \ SUM$보다 하나가 크다면 어떻게 될까?

 

예를 들어, 1, 2, 4과 같이 주어진다면 다음과 같이 분배할 수 있을 것이다.

 

4개짜리 타기 -> 2개짜리 타기 -> 4개짜리 타기 -> 2개짜리 타기 -> 4개짜리 타기 -> 1개짜리 타기 -> 4개짜리 타기

이렇게 적절하게 분배하여 모든 이용횟수를 소진시킬 수 있다.

 

 

만약 $MAX$의 이용 횟수가 $OTHER \ SUM$보다 둘 이상이 크다면 어떻게 될까?

 

예를 들어, 1, 2, 5와 같이 주어진다면 다음과 같이 분배할 수 있다.

 

5개짜리 타기 -> 2개짜리 타기 -> 5개짜리 타기 -> 2개짜리 타기 -> 5개짜리 타기 -> 1개짜리 타기 -> 5개짜리 타기 (이후 더 이상 탈 수 없음)

따라서, 최대한 교대로 하여 놀이기구를 이용한다고 해도 $MAX$의 이용 횟수가 남은 채로 끝낼 수밖에 없다.

 

그리고 이 횟수는 $(OTHER \ SUM)*2 + 1$회라는 사실을 알 수 있다.

 

 

따라서, 결론을 내리면, $MAX \leq OTHER \ SUM + 1$일 때라면, $MAX$를 중심으로 교대로 왔다 갔다 하며 모든 이용 횟수를 소진시킬 수 있다.

 

그게 아닌 경우라면 전부 소진시킬 수 없는데, 그 횟수는 $(OTHER \ SUM)*2 + 1$회이다.

 

이를 그대로 구현하면 끝이다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 25635번 자유 이용권
# 그리디, 정렬
'''
접근 방법:
예제 입력 1
1, 1, 3  -> 0
1, 1, 2  -> 1
1, 0, 1  -> 2
1, 0, 0  -> 3
0, 0, 0  -> 4
예제 입력 2
3, 5  -> 0
3, 4  -> 1
2, 4  -> 2
2, 3  -> 3
1, 3  -> 4
1, 2  -> 5
0, 2  -> 6
0, 1  -> 7
예제 입력 3
2, 2, 2, 3  -> 0
2, 2, 2, 2  -> 1
2, 2, 1, 2  -> 2
2, 2, 1, 1  -> 3
2, 1, 1, 1  -> 4
1, 1, 1, 1  -> 5
...
'''
import sys
input = sys.stdin.readline
N = int(input())
A = sorted(map(int, input().rstrip().split()))
if N == 1:
    print(1)
elif A[-1] <= sum(A[:N-1])+1:
    print(sum(A))
else:
    print(sum(A[:N-1])*2+1)