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

 

SW Expert Academy

 

---

🗒️파이썬 코드 풀이

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

    ans = "Possible"      
    lst.sort() 
    cnt = 0 

    for t in lst :
        cnt += 1
        if (t//M)*K < cnt : 
            ans = "Imposible"
            break
    
    print(f"#{tc} {ans}")

 

1. 기본값은 Possible로 한다

 

2. 크기순으로 sort 정렬을 해준다. (먼저 오는 손님에게 붕어빵 먼저 제공)

 

3. 손님들의 도착시간 리스트로 for문을 돌려준다. 

 

4. 손님 수 + 1

 

5. 순차적으로 오는 사람에게 붕어빵 제공이 가능한지 체크 ((도착시간//M초) * M초 뒤 붕어빵 수) 

 

5. 한명이라도 지급이 안되면 Impossible로 변경 후 break

 

🚨 생각 오류

ans = "Impossible"      
lst.sort()

if (lst[-1] // M) * K >= len(lst):
    ans = "Possible"

 

마지막 사람만 붕어빵 제공 가능하면 다 줄 수 있는거 아닌가해서, 마지막 기준으로 판단했다.

 

반례 ) 

-  N=100, M=100,K=50 (100초에 50개 붕어빵을 만듬 )

-  사람들 도착 시간 : [3,5,7 ... 101 ]  (총  50명)

=> 이렇게 했을 경우 마지막 사람 기준으로  if 문은 성공한다.

하지만 마지막 사람만 제 시간에 받지, 앞에 사람은 제 시간에 받지 못한다.

 

📑 내가 쓴 코드

T = int(input())
for tc in range(1,T+1) :
    N,M,K = map(int,input().split())
    lst = list(map(int,input().split())) 
    ans = "Possible"
    
    cnt,second = 0,0 # M초만큼 만들어내는 수,  초(시간)
    
    for k in lst :  # 준비시간 보다 빨리 오는 사람 제거 (가지치기)
        if k < M :
            ans = "Impossible"        
        
    if ans == "Possible" :
        while lst : 
            second += 1 
            if second == M :  # M 초의 시간이 지나면 cnt(붕어빵) K 만큼 증가, second 초기화
                second = 0 
                cnt += K

            pop_lst = []
            for i in range(len(lst)): 
                lst[i] -= 1 # 1초씩 차감
                if lst[i] == 0 : # 만약 i번째 손님이 0(순번이 오면) 붕어빵 나눠 줌 (-1)
                    cnt -= 1
                    pop_lst.append(i)

            for k in range(len(pop_lst)):  # 대기 시간이 0초인 손님 내보내기                
                lst.pop(lst.index(0))
            
            if cnt < 0:  # 손님 차례인데 붕어빵이 0보다 작으면 Impossible
                ans = "Impossible"

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

 

먼저 준비시간 보다 빨리 오는 사람은 가지치기를 해준다

 

기본 상태는 Possible로 해두고, 카운트를 하나 하나 줄여가는 식으로 했다.

그리고 cnt 변수는 M초의 시간이 지날때마다 K개를 늘려간다.

 

만일 손님도착 리스트에 0이 있으면 cnt(붕어빵)을 -1 하고, pop_lst에 index를 넣어준다.

(바로 pop을 하면 반복문 도중 크기가 바꿔져서, pop_lst에 넣어주었다.)

 

그리고 pop_lst를 반복문 돌려, 0인 크기를 가진 값을 pop 해준다.

 

만일 cnt의 값이 음수이면, 손님 도착시간을 못 맞춘것이기 때문에 Impossible이 된다.

 

🚨 생각 오류

for k in range(len(pop_lst)):
	lst.pop(lst.index(0))

 

사실 이 부분에서 엄청 애먹었다. 

 

for k in pop_lst :
	lst.pop(k)

 

맨 처음 실행했던 코드는 위와 같은 코드이다.

대부분 되는데, 특정 배열에서는 무한루프를 돌고 있었다.

 

ex )  [345 331 0 0 34 5 6]

바로 이런 경우가 무한루프를 돌고 있는 케이스다. 

pop_lst에서 값이 0인 인덱스의 위치는 [3,4]로 정해져있다. 

 

순차적으로 pop을 진행 시키면 [345 331 0  34 5 6] -> [345 331 0 5 6] 가 되는 것이다.

즉, pop으로인해 배열의 순서가 바꿨고 그로인해 값이 0인 인덱스 위치가 바뀐것이다.

 

이를 방지하려고 lst 배열의 크기가 바뀔때마다 lst.index(0)를 사용하여  찾아주었다.

 

🧐 내 생각 정리

이 문제는 이해만 한참 걸렸다.  

N=2,M=2,K=1  / [3 2] 일때,  3초뒤에 사람이 오고 나간 후, 2초 뒤에 다음 사람이 오는거라 생각했다.

이게 왜 Impossible인지 이해 할 수 없었다.  ( 3초 안에 1개 만들고, 뒤에 사람은 5초 뒤에 오니까 충분한데 ..? )

이 문제 포인트는 손님들의 도착 시간을 각각 독립적으로 봐야 한다는 것이다.

 

실제 코드를 작성하면서 예상치 못한 변수들이 나와 시간을 너무 많이 썼다.  ex) pop_lst

항상 간결하게 문제를 구조화하고 축약해서 생각 할 수 있도록 해야겠다.

---

📚문제

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

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

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

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

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

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

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

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

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


[입력]

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

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

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

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


[출력]

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

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


[예제 풀이]

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

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

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