문제 링크

문제 설명

한 버스에 3(C)명씩 태울 수 있고, 탑승객은 손님은 1, 2, 3, 6, 12초에 한명씩 오는데, 각각 5초(K)씩 기다릴 수 있다. 1초에 온 사람은 6초까지 기다릴 수 있고, 2초에 온 사람은 7초까지 기다릴 수 있는 뭐 이런식이다. 이때 필요한 최소한의 버스는 몇대인가?

예시

[input]
5 3 5
1
2
3
6
12

[output]
3

[input]
6 3 3
7
6
2
8
10
6

[output]
3

사고의 흐름

1 2 3 6 12초에 온다.. 그러면 버스가 1초에 오면 한명밖에 못태우네, 한,,4초에 오면 되겠다. 그러면 3명 태울 수 있고 1, 2, 3초에 온사람들도 기다리다가 버스가 와서 타겠지. 6초에는 안타깝게도 버스 1대가 필요하다. 한 7초에만 와도 12초에 버스 보내서 두명을 한꺼번에 태울 수 있었는데,,, 아쉽지만 12초를위한 버스 한대 더 추가 해서 총 3대가 된다. 다시말해서 최대한 손님들을 기다리게 한다음에 버스를 태우면 될것같다. 근데 이게,, 앞에서 부터 태우면 자칫하다간 최소가 안될수도 있겠다. 예를들어서, 1 3 12

모범답안

1. 여기를 누르면 답이 보입니다
def answer(n, c, k, ts):
    ts.sort()
    bus = 1
    _c = 1
    standard = ts[0]
    for i in range(1, len(ts)):
        if ts[i] <= standard+k and _c < c:
            _c += 1
        else:
            _c = 1
            standard = ts[i]
            bus += 1
    return bus
    
n, c, k = map(int, input().split())
ts = []
for _ in range(n):
    ts.append(int(input()))
print(answer(n, c, k, ts))
2. 여기를 누르면 답이 보입니다