PS Featured

[PS] BOJ 24508 / 나도리팡

Minjun Kim

10 Jan 2026 • 2 min read

Thumbnail: Photo from 백준 24508

문제 링크: https://www.acmicpc.net/problem/24508

풀이

한 바구니에서 다른 바구니로 나도리 1마리를 올기는 행동을 최대 $T$회 반복했을 때 모든 나도리를 터뜨릴 수 있는지 파악해야 합니다. 나도리는 한 바구니에 $K$마리가 모이면 터지며 사라집니다.

한 바구니에 나도리를 $K$마리 채우려 할 때, 수가 적은 바구니에서 많은 바구니 쪽으로 나도리를 옮기는 편이 이동 횟수가 더 적습니다. 따라서, 전체 바구니를 내림차순으로 정렬한 뒤 나도리를 옮기도록 구현했습니다.

나도리를 채울 바구니를 앞에서부터, 나도리를 옮길 바구니를 뒤에서부터 투 포인터 방식으로 반복하며 최대한 많은 나도리를 터뜨려 봅니다. 이후, 더 이상 나도리를 옮길 수 없을 때 결과를 출력합니다.

나도리를 더 이상 옮길 수 없는 조건은 다음과 같습니다:

이동 횟수 $T$를 다 사용했을 경우
모든 나도리가 터져 사라졌을 경우

나도리의 이동 과정에서 터뜨린 나도리의 수를 기록한 뒤, 결과 출력 시 전체 나도리의 수와 비교해 결과를 출력했습니다.

전체 코드

input = open(0).readline

N, K, T = map(int, input().split())
nadories = sorted(map(int, input().split()), reverse=True)
total_nadories = sum(nadories)

s = 0
e = N - 1
popped = 0
while s < e:
    while T > 0 and nadories[e] > 0 and nadories[s] < K:
        T -= 1
        nadories[e] -= 1
        nadories[s] += 1
    
    if nadories[s] == K:
        s += 1
        popped += K
    if nadories[e] == 0:
        e -= 1
    
    if T == 0:
        break

print("YES" if popped == total_nadories else "NO")

solution.py