BOJ 3060 - 욕심쟁이 돼지

문제

BOJ 3060 - 욕심쟁이 돼지

6개의 먹이통이 원형으로 놓여 있다. 매일 각 먹이통에는 나머지 5개 먹이통에 있는 먹이의 합만큼 새로운 먹이가 추가된다. N이 주어졌을 때, 총 먹이의 합이 처음으로 N을 초과하는 날이 며칠째인지 구하라.

입력

첫 줄에 테스트 케이스 수 T가 주어진다. 각 테스트 케이스는 두 줄로, 첫 줄에 N, 둘째 줄에 6개 먹이통의 초기값이 주어진다.

출력

각 테스트 케이스마다 총 먹이의 합이 N을 초과하는 최초의 날을 출력한다.

예제

풀이

매일 총 먹이량이 4배씩 증가하는 규칙을 이용하여 N을 초과하는 날을 구한다.

1. 6개 먹이통의 합을 구한다
2. 매일 각 먹이통에 나머지 5개의 합이 추가되므로, 총합은 합 + 6 x (합 - 자신의 양)의 합이 된다
3. 이를 정리하면 매일 총합이 정확히 4배가 된다 (각 먹이통에 나머지 5개의 합이 추가 = 총합 x 5 - 자신 x 5를 각각 더하면 총합 x 4)
4. 총합 x 4^k > N이 되는 최소 k를 구한다
5. 1일째부터 시작하므로 k + 1을 출력한다

핵심 아이디어: 각 먹이통에 나머지 5개의 합이 추가되면, 전체 합이 매일 정확히 4배로 증가한다. 이를 통해 반복 횟수를 로그적으로 구할 수 있다.

코드

t = int(input())
for _ in range(t):
    n = int(input())
    line = list(map(int, input().split()))
    total = sum(line)
    count = 0
    while n >= total:
        count += 1
        total *= 4
    print(count + 1)

복잡도

• 시간: O(log N) — 총합이 4배씩 증가하므로 반복 횟수가 로그적
• 공간: O(1) — 고정 크기 변수만 사용