[Python, 파이썬] SWEA 1860. 진기의 최고급 붕어빵

M초의 시간을 들이면 K개의 붕어빵을 만들수 있다.
손님들이 도착하는 시간이 주어질 때,모든 손님들에게 기다리는 시간없이 붕어빵을 제공할 수 있는지 판별하는 문제.

 

 

T = int(input()) # 테스트 케이스 개수 T

for test_case in range(1, T+1):

    N, M, K = map(int, input().split()) # 손님 수 N, 시간 M, 붕어빵 개수 K
    time = list(map(int, input().split())) # 손님이 도착하는 시간
    use = 1 # 필요한 붕어빵 개수
    check = 'Possible'

    time.sort() # 도착하는 시간 정렬

    for t in time:
        
        if((t//M)*K < use): # 붕어빵이 부족하면
            check = 'Impossible'
        use += 1 # 필요 개수 +1
                       
        
    print("#%d %s" %(test_case, check))

 

 

 

[문제풀이]

---

손님이 도착하는 시간을 우선 먼저 도착하는 순서대로 sort를 사용해 정렬한다.

그 후, 도착하는 시간에 만든 붕어빵의 개수가 필요로 하는 개수보다 많은 지 검사한다.

 

(t//M)*K < use

 

 

손님이 도착하는 시간을 t라 하자.

붕어빵을 만드는 시간이 M이므로, (t//M)번이 손님이 도착할 때까지 돌릴 수 있는 사이클의 수다.

이때 M초마다 K를 만들 수 있으므로, 구한 값에 K를 곱한 수가 손님이 도착하는 시간 내에 만들 수 있는 붕어빵의 개수다.

 

이게 use보다 크면 붕어빵 판매가 딜레이 없이 가능하고, 작으면 붕어빵이 부족한것!

비교해서 부족할 때 Impossible을 출력하도록 하면 된다.