[SWEA] 1860 진기의 최고급 붕어빵

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LsaaqDzYDFAXc 

SW Expert Academy

 

처음에 푼 풀이

도착시간 // 제조시간*붕어빵 = 총 붕어빵 수

1. 도착 시간이 제조시간 보다 빠르면 NO

2. 총 붕어빵 수 -1 씩 해서 붕어빵 수가 음수면 Impossible / 아니면 Possible

이렇게 2가지 생각하고 풀었는데, Test Case가 1000개중 997개만 맞았다.

왜그럴까 했는데

붕어빵을 95초에 1개씩 만들고, 145 - 200 - 225 이렇게 오면

200초에 2개 만들어진 붕어빵 2개가 145, 200을 거쳐서 다떨어져서 없는데

225만 봐서는 2개가 만들어졌고, 혼자 와서 붕어빵을 가져갈 수 있다고 뜨는 것이다..

오는 손님 시간 순서를 정렬 안하고 풀었더니 이렇게 되었다.

T = int(input())
for test_case in range(1,T+1):
    # N명의 사람 / M초 동안 K개의 붕어빵
    # N명의 사람의 도착시간
    # 모든 손님에게 붕어빵을 제공할 수 있는지
    N, M, K = map(int,input().split())
    time = list(map(int,input().split()))
    ans = 0
    for i in range(N):
        # 만들기 전에 도착하면 X
        if time[i] < M:
            ans += 1
        # 만든 후에 도착
        else:
            # time이 M의 배수보다 크면
            if time[i]//M > 0:
                # M의 배수 만큼 K 증가
                K = K*(time[i]//M)
                K -= 1
            else:
                K -= 1
    # 만들어지는 붕어빵이 모자라면
    if K < 0:
        ans += 1
    if ans == 0 :
        print(f'#{test_case} Possible')
    else:
        print(f'#{test_case} Impossible')

 

시간 정렬을 하고 아예 다시 풀기로함

(도착시간//제조시간)*(붕어빵제조개수) - 방문한 사람수 < 0 이면 Impossible

반복문으로 금방 풀 수 있는 문제였다.

복잡하게 생각하지 말것 !!!

T = int(input())
for test_case in range(1,T+1):
    # N명의 사람 / M초 동안 K개의 붕어빵
    N, M, K = map(int, input().split())
    # N명의 사람의 도착시간
    time = list(map(int, input().split()))
    # 시간순으로 정렬
    time = sorted(time)
    ans = 0
    for i in range(N):
        if time[i] < M:
            ans = 1
            break
    for i in range(N):
        # 붕어빵수에서 손님수를 뺐을 때, 음수면 불가능
        # 손님은 1번 부터
        if (time[i]//M)*K-(i+1) < 0:
            ans = 1
            break
    # ans = 0 이면 모든 손님에게 붕어빵을 제공가능
    if ans == 0 :
        print(f'#{test_case} Possible')
    else:
        print(f'#{test_case} Impossible')