문제풀이/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개의 꽥꽥을 모두 둘러보면 답을 구할 수 있다.