[SWEA][D3][#01860] 진기의 최고급 붕어빵

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

진기는 붕어빵 가게를 운영하고 있다.

진기가 파는 붕어빵은 그냥 붕어빵이 아니라 겉은 바삭! 속은 말랑! 한입 물면 팥 앙금이 주르륵 흘러 입안에서 춤을 추며,

절로 어릴 적 호호 불며 먹었던 뜨거운 붕어빵의 추억이 떠올라 눈물이 나오게 되는 최고급 붕어빵이다.

진기는 이런 붕어빵을 보통 사람들에게는 팔지 않는다.

그는 무조건 예약제로만 손님을 받으며, 예약을 하려는 손님들은 진기의 까다로운 자격 검증에서 합격해야만 붕어빵을 맛 볼 자격을 얻는다.

그래서 오늘은 N명의 사람이 자격을 얻었다.

진기는 0초부터 붕어빵을 만들기 시작하며, M초의 시간을 들이면 K개의 붕어빵을 만들 수 있다.

서빙은 진기가 하는 것이 아니기 때문에, 붕어빵이 완성되면 어떤 시간 지연도 없이 다음 붕어빵 만들기를 시작할 수 있다.

0초 이후에 손님들이 언제 도착하는지 주어지면, 모든 손님들에게 기다리는 시간없이 붕어빵을 제공할 수 있는지 판별하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 세 자연수 N, M, K(1 ≤ N, M, K ≤ 100)가 공백으로 구분되어 주어진다.

두 번째 줄에는 N개의 정수가 공백으로 구분되어 주어지며,

각 정수는 각 사람이 언제 도착하는지를 초 단위로 나타낸다. 각 수는 0이상 11,111이하이다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

모든 손님에 대해 기다리는 시간이 없이 붕어빵을 제공할 수 있으면 “Possible”을, 아니라면 “Impossible”을 출력한다.

예제

입력

4
2 2 2
3 4
2 2 2
1 2
2 2 1
4 2
2 2 1
3 2

출력

#1 Possible
#2 Impossible
#3 Possible
#4 Impossible

2번째 테스트 케이스의 경우, 2초가 지날 때마다 붕어빵을 2개씩 만들 수 있다.

하지만 손님 1명은 1초에 도착하므로 이 손님에게는 붕어빵을 바로 제공할 수 없다.

따라서 결과값으로 Impossible 출력한다.

My Sol

T = int(input())
for tc in range(1, T+1):
    ans = 'Possible'
    N, M, K = map(int, input().split())

    p = list(map(int, input().split()))
    for i in range(N-1, -1, -1):
        for j in range(i):
            if p[j+1] < p[j]:
                p[j], p[j+1] = p[j+1], p[j]
    p = [0] + p

    for i in range(1, N+1):
        if (p[i]//M)*K < i:
            ans = 'Impossible'
            break

    print(f'#{tc} {ans}')

붕어빵을 사러 오는 손님들의 시각이 정렬되어있지 않으므로 정렬을 해주어야 한다. 이때 손님은 최대 100명이므로 버블정렬을 사용해도 시간이 크게 늘어나지 않을 것 같아서 편의를 생각해 버블 정렬으로 오름차순 정렬하였다. 그리고 인덱스 계산의 편의를 위해 손님 배열 p의 앞에 [0]을 추가해주었다.

p[i]는 i번째 오는 손님이다. 특정 i의 i번째 손님이 올 때는 누적 붕어빵의 개수가 못해도 i개는 되어야 한다. M분당 K개의 붕어빵을 만드는데, 1분당 K/M개를 만드는 것이 아니라, 각 M분마다 K개의 붕어빵이 생산되는 것이므로, (p[i]//M) 몫으로 처리하여 p[i], 즉 i번째 사람이 도착하는 시간이 M분 보다도 전이라면 붕어빵은 0개이므로 0개가 되는 것이고, M분당 정확히 늘어날 수 있도록 (p[i]//M)*K 으로 처리한 것이다. 이것이 i보다 작으면 실패한 것이므로 ‘Possible’로 저장된 ans를 ‘Impossible’로 재정의한다. 이후 이를 출력 형식에 맞춰 출력한다.

결과

PASS