백준 25635 자유 이용권 [BOJ 25635] python

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

25635번: 자유 이용권

접근 방법

• 처음에 볼 때 바로 생각나는건 방문 배열을 이용해서 방문 하지 않은 원소들 중 최대값인 원소를 1 줄이고, 타는 횟수를 1늘리는 것이었다. 그 코드가 아래였다.

N = int(input())
play_count = list(map(int, input().split()))
cnt = 0

is_played = [False for _ in range(N)]
max_idx = 0
prev_max_idx = 0
while True:
    # 이용하지 않았고, 남은 횟수가 0이 아닌 놀이기구 횟수들을 list에 추가한다.
    playable_list = []
    max_data = -1

    for i in range(N):
        if not is_played[i] and play_count[i] != 0:
            playable_list.append(play_count[i])

            if play_count[i] > max_data:
                max_data = play_count[i]
                max_idx = i

    # 이용하지 않았고, 남은 횟수가 0이 아닌 놀이기구 횟수가 없다면 break 또는 놀 수 있는 기구가 하나만 남는다면 break
    if not playable_list:
        break

    # 이전에 탄 놀이기구는 playable_list에 추가되지 않았으므로, 다음에 조회할 때 다시 탈 수 있다.
    is_played[prev_max_idx] = False
    is_played[max_idx] = True
    play_count[max_idx] -= 1

    prev_max_idx = max_idx
    cnt += 1

print(cnt)

• 하지만 이 방식은 위 문제 조건인 a_i 가 10억의 값을 가지는 것 때문에 무조건 Time Out이 나온다.
• 위에 주어진 예제로는 바로 답을 내기가 힘들어 여러 예제들을 생각해보았다.
• 계속 해보다가 문득 하나를 알 수 있었는데 모두 탈 수 있는 경우에는 a_i들의 합이 곧 탈 수 있는 최대 값이 된다. 이것은 매우 당연하게 모두 탈 수 있는 경우엔 모두 타면 되니까
• 하지만 위에 두 번째 예제 입력처럼 횟수가 남아도 중복된 놀이기구를 탈 수 없다는 조건에 의해 타지 못하는 경우가 생기는데 이것이 발생할 수 있는 조건은 다음과 같다. 이때 A는 놀이기구 이용 횟수 제한을 모은 배열이고 이 배열이 정렬되었음을 가정한다. N은 배열의 길이를 나타낸다.

$$A[0] - \sum_{i=1}^{N - 1}A[i] \geq 2$$

 

• 만약 저 식의 결과가 2보다 작다면, 모든 놀이기구를 탈 수 있는 경우이므로 배열 A의 모든 원소를 합한 것이 답이 된다.
• 만약 2 이상이라면, 이용할 수 없게 되는 횟수는 다음과 같다.

$$A[0] - \sum_{i=1}^{N - 1}A[i] - 1$$

• 2 이상일 때의 이용할 수 없게 되는 횟수가 위와 같으므로 총 이용 가능한 최대 횟수는 A의 모든 원소를 합한 것에서 위의 값을 빼는 것이다 즉, 아래의 식과 같게 된다.

$$T = A[0] + \sum_{i=1}^{N - 1} A[i] - (A[0] - \sum_{i=1}^{N - 1}A[i] - 1)$$ 

 

식을 정리하면

$$T = 2\sum_{i=1}^{N-1}A[i] + 1$$

이 되고 이를 그대로 코드로 옮기면 된다. 정답 코드는 아래와 같다.

 

N = int(input())
play_count = list(map(int, input().split()))
play_count.sort(reverse=True)

# 탈 수 있는게 1개 말곤 없는 경우 무조건 그 하나만 타고 끝이다
if N == 1:
    print(1)
    exit(0)

sm = sum(play_count[1:])

# 가장 큰 이용횟수와 그 이전까지의 이용횟수의 합의 차이가 2 미만이라면 어떠한 경우에도 모두 탈 수 있다.
if play_count[0] - sm < 2:
    print(sm + play_count[0])
else:
    # 가장 큰 이용횟수와 그 이전까지의 이용횟수의 합의 차이가 2 이상이 날 시, 온전히 다 타지 못한다.
    # 온전히 다 타지 못하는 횟수는 위의 두 차이 - 1 만큼 된다.
    # 즉 sm + play_count[0] - (play_count[0] - sm - 1) 이 되고 이를 정리하면 (2 * sm) + 1이 된다.
    print((2 * sm) + 1)

• 위 방식을 사용하면 정렬 및 1부터 N - 1까지의 합만 계산하면 되므로 시간복잡도는 다음과 같다 $$O(N\log N)$$