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

2024년 5월 10일

문제 링크 : SWEA 1860번 - 진기의 최고급 붕어빵

SW Expert Academy

 

---

 

 

문제 접근

 

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

 

손님이 도착하는 시간이 각각 주어졌을 때, 모든 손님이 붕어빵을 먹을 수 있으면 Possible, 한 명이라도 못먹는다면 Impossible을 출력하는 문제이다.

 

여기서 우리가 조심해야 하는 점은 손님이 0초에 올 수 있다는 점이다.(마치 오픈런)

 

1초 단위로 시간이 흐를 때마다 갱신되는 붕어빵의 개수와 손님의 도착, 그리고 손님이 붕어빵을 먹을 수 있는지 알아야하기 때문에 단순 구현 문제라고 판단했다.

 

손님의 도착 순서가 무작위로 주어지고, 어차피 손님은 시간 순서대로 도착하기 때문에 입력받은 손님의 도착 시간을 오름차순 정렬하여 1초 단위로 시간이 흐를 때마다 붕어빵을 먹을 수 있는지 없는지 판단하면 된다.

 

---

 

입력 예시 중 하나를 이용해 흐름도를 시각적으로 보자.

 

초기 상태 : time = 0

초기 상태

 

N = 2, M = 2, K = 2 이며, 방문 손님이 각각 4, 3의 시간에 방문하는 예시로 설명을 이어가겠다.

 

방문 예정 손님은 오름차순으로 정렬해 두었다.

 

time을 1씩 증가시키며, 해당 시간에 붕어빵이 만들어지면 K만큼 fish_bread를 증가시키고, 이 때 방문 손님이 있다면 fish_bread를 1 감소시키며 만약 fish_bread가 0이라 구매하지 못한다면 Impossible을, 모두 구매가 가능하다면 Possible을 도출해야 한다.

 

참고로, 손님이 time = 0에 방문할 수 있으므로 구현 시 조건문을 잘 걸어두어야 한다.

 

 

time = 1

 

 

M = 2 이므로 time이 2의 배수일 때마다 붕어빵이 만들어지기에 아직 붕어빵은 제작되지 않았으며, queue의 첫 번째 요소가 3 이므로 아직 손님이 방문하지 않았다.

 

아무 일도 일어나지 않을 시간이므로 time을 1 증가시켜보자.

 

time = 2

 

 

 

time이 M의 배수이므로 붕어빵이 K개 만들어질 것이다. fish_bread를 2 증가시키고, 방문 손님이 있는지 확인해보자.

 

방문 손님이 없으므로 time을 1 증가시켜보자.

 

 

time = 3

 

 

 

붕어빵은 만들어지지 못하며, 방문 손님이 있는지 보니 queue의 첫 번째 요소가 3이므로 손님이 한 명 방문할 시간이다.

 

현재 방문 손님의 상태를 담아두는 now_arrive에 해당 손님을 append 해주고, queue.popleft()로 방문 예정 손님 리스트에서 해당 손님을 제외시킨다.

 

 

현재 시간에 맞춰 방문할 손님을 모두 now_arrive에 append 시켜줬다면, 한 명씩 pop하며 fish_bread를 1씩 감소시킨다.

 

 

 

만약 여기서 fish_bread가 0인데 now_arrive에 손님이 남아있다면, 그 손님은 붕어빵을 구매 못하는 것이기에 Impossible을 출력하면 될 것이다.

 

지금은 구매가 가능하며 현재 방문 손님은 1명이니 fish_bread를 1 감소시킨다.

 

 

이후 더 구매할 손님이 없으므로 time을 1 증가시킨다.

 

 

time = 4

 

 

time이 M의 배수이므로 붕어빵이 만들어졌기에 fish_bread를 K만큼 증가시킨다.

 

 

또한 손님이 도착할 시간이므로 now_arrive에 해당 손님을 append하고 queue의 첫 번째 요소를 popleft() 해준다.

 

 

now_arrive에 존재하는 모든 손님이 fish_bread를 구매 가능한지 확인하며, 가능하다면 fish_bread를 1씩 감소시키며 now_arrive를 하나씩 pop() 해준다.

 

 

 

 

모든 방문 예정 손님이 구매를 마쳤다면 Possible을 출력해주며 로직을 종료한다.

 

 

Impossible인 경우는 어떨까?

 

 

time = 0

 

N = 2, M = 2, K = 2 이며, 방문 손님이 각각 1, 2의 시간에 방문하는 예시로 설명을 이어가겠다.

 

 

time = 1

 

 

time이 1이 되어 방문 손님이 존재하나, 붕어빵이 없기 때문에 Impossible을 출력하고 로직을 종료한다.

---

 

순서도

 

1. 입력 값을 입력 받고, 
현재 시간인 time, 붕어빵 개수인 fish_bread, 
현재 방문 고객인 now_arrive, 
방문 예정 고객인 queue를 선언한다.
time의 초기 값은 0이며, queue에 저장된 고객 정보들은 시간 순서대로 오름차순 정렬한다.

2. time을 1 증가시킬 때마다 붕어빵의 개수가 갱신될 수 있는지, 만약 방문 고객이 있다면 붕어빵을 살 수 있는지 확인한다.

3. 모든 고객이 붕어빵을 살 수 있었다면 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

 

---

 

 

주의할 점

 

붕어빵이 만들어지는 시간에 손님이 오는 경우, 붕어빵이 만들어지는 것이 우선순위이기 때문에 붕어빵 개수를 갱신시키고 손님에게 붕어빵을 파는 순서로 로직을 구성해야 한다.

---

 

전체 코드

 

from collections import deque

def solution():
    arr = list(map(int, input().split()))
    queue = deque(sorted(arr))

    # 마지막 손님이 오는 시간(종료 조건으로 사용)
    last = queue[-1]
    # 현재 붕어빵 개수
    fish_bread = 0
    # 흐른 시간
    time = 0

    while time <= last:
        if time != 0 and time % M == 0:
            fish_bread += K
        
        now_arrive = []
        while queue:
            if queue[0] == time:
                now_arrive.append(queue.popleft())
            else:
                break
        
        while now_arrive:
            if fish_bread <= 0:
                return "Impossible"
            now_arrive.pop()
            fish_bread -= 1
        
        time += 1
    
    return "Possible"


T = int(input())

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

    print(f'#{test_case} {solution()}')

---

 

풀이 후기

 

단순 구현 문제였기에 어려움이 없었다.