문제풀이/Greedy

[Python/파이썬] 백준 30404번 오리와 박수치는 춘배

딜레이레이 2025. 4. 4. 15:20

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

코드

n, k = map(int, input().split())
kkwaeg = list(map(int, input().split()))

idx = 0
answer = 0
while idx < n:
    time = kkwaeg[idx]
    answer += 1
    idx += 1
    while idx < n and kkwaeg[idx] <= time+k:
        idx += 1
print(answer)

 

한 번 박수를 칠 때 가능한 모든 꽥꽥을 커버칠 수 있게 한다고 생각하면 된다.

예를 들어, k=4이고 꽥꽥소리를 3초, 5초, 7초에 한 번씩 낸다면 7초에 한 번 치는 것만으로도 3번의 꽥꽥을 커버할 수 있게 된다. 

 

어떤 꽥꽥으로부터 k 이하의 거리에 있는 것들은 같이 친다고 보면 다음과 같이 코드를 구현할 수 있다.

time = kkwaeg[idx]
answer += 1
idx += 1
while idx < n and kkwaeg[idx] <= time+k:
    idx += 1

time은 함께 처리할 꽥꽥 중 가장 먼저 오는 꽥꽥이다. 이 꽥꽥으로부터 idx를 +1해가며 K초 이내에 있는 것들은 같은 박수 한 번으로 묶는 과정이라고 보면 된다.

 

이렇게 idx를 +1해가며 n개의 꽥꽥을 모두 둘러보면 답을 구할 수 있다.