[BOJ] 귤나무 (31005, G1)

이번 문제는 상당히 어려운 문제입니다. 어려운 알고리즘을 쓰진 않지만, 최적화를 잘 해야 합니다.

문제 내용

 

풀이 과정

우선 문제를 이해해 봅시다. 순서대로, 귤을 가져갑니다. 못 가져가면 아무것도 못하고 다음 애가 가져갑니다... 반복합니다.

아무도 귤을 못 가져가는 순간이 옵니다. 그 대로 저 날짜까지 가면 됩니다. 대략 숫자 범위를 보면, 최악의 케이스여도 대충, 20만 * 10^18 * 10^12 잡아도  10^100보다는 확실히 작습니다. 따라서 10^100은 크게 고려하지 않아도 될 거 같습니다.

즉 문제는, 마지막에 몇 개가 남을 것인가? 에 집중하면 됩니다. 이를 역으로 생각해 봅시다.

곰곰이들 중, 과일을 가장 적게 원하는 애가 있을 것입니다. 그 애가 원하는 것보다 과일이 더 적게 남는다면? 남은 상태로 갈 것입니다. 이걸 구하라는 거네요.

문제는, 순서대로 곰곰이들이 귤을 가져가기에 개수를 정렬하거나 하는 행위는 불가능합니다. 어떻게 해야 할까요? 자신이 귤을 가져갈 수가 없다면 영구히 대열에서 빠지면 됩니다. 하지만 단순히 이렇게 해서 무한 반복하면 대열이 길고 가져가는 귤은 적은데 귤이 너무 많이 있다면? 시간 초과가 발생합니다. 

처음부터 다시 생각해봅시다. 모두가 귤을 가져가는 것을 굳이 계속 지켜보고 세고 있어야 할까요? 이 반복과정을 생략해 줄 수 있습니다. 이는 나머지 계산으로 커버 됩니다.

이를 계속 고려해 주면 됩니다. 누군가가 귤을 못 가져가서 탈락해버린다면, 나머지 인원이 가져갈 수 있는 귤의 합 만큼 계속 돌 거니 나머지 계산을 또 시켜 줍니다. 이것이 가능한 이유는 순서대로 가져가기 때문입니다.

 

 

순서대로 가져가는 것을 구현하기 위해? 큐를 사용하면 됩니다!  자료구조 + 수학이 담겨 있는 즐거운 문제입니다.

import sys
from collections import deque
input = sys.stdin.readline
bugs, fruits = map(int, input().split())
num_list = list(map(int, input().split()))
left_fruit  = fruits % sum(num_list)
queue = deque()
left_bug_sum = 0
for n in num_list:
    if n <= left_fruit:
        queue.append(n)
        left_bug_sum += n
# 우선 나머지로 모두 다 돌 수 있게 처리를 한번 하자.

# queue = 0 -> 애초에 아무도 이제 못먹는다.
if len(queue) == 0:
    print(left_fruit)
else:
    left_cycle_cnt = left_fruit // left_bug_sum
    left_fruit = left_fruit - left_cycle_cnt * left_bug_sum

    while len(queue) > 1:
        cur_bug = queue.popleft()
        if cur_bug <= left_fruit:
            left_fruit -= cur_bug
            queue.append(cur_bug)
        else:
            # 못 가져갈 경우에는 곰곰이 명단에서 빼고 합산에서도 뺜다.
            left_bug_sum -= cur_bug
            # 반복 안 시키게 나머지 계산을 시킨다.
            if left_bug_sum > 0:
                left_fruit %= left_bug_sum
        # 곰곰이 전원 탈락 / 과일 없음
        if left_fruit == 0 or left_bug_sum == 0:
            break
    # 과일을 다 먹어서 끝남.
    if left_fruit == 0:
        print(0)
    # 모든 곰곰이가 못먹는다. 나머지를 준다.
    elif left_bug_sum == 0:
        print(left_fruit)
    # 딱 한마리 남은건 최소값일 것이다. 무조건. 혼자 계속 그 개수 가져가게. 
    else:
        print (left_fruit % queue[0])