[SWEA] 5099_피자 굽기

📕 문제

N개의 피자를 동시에 구울 수 있는 화덕이 있다. 피자는 치즈가 모두 녹으면 화덕에서 꺼내며, 치즈의 양은 피자마다 다르다.
1번부터 M번까지 M개의 피자를 순서대로 화덕에 넣을 때, 치즈의 양에 따라 녹는 시간이 다르기 때문에 꺼내지는 순서는 바뀔 수 있다.
주어진 조건에 따라 피자를 구울 때, 화덕에 가장 마지막까지 남아있는 피자 번호를 알아내는 프로그램을 작성하시오.

- 피자는 1번위치에서 넣거나 뺄 수 있다.
- 화덕 내부의 피자받침은 천천히 회전해서 1번에서 잠시 꺼내 치즈를 확인하고 다시 같은 자리에 넣을 수 있다.
- M개의 피자에 처음 뿌려진 치즈의 양이 주어지고, 화덕을 한 바퀴 돌 때 녹지않은 치즈의 양은 반으로 줄어든다. 이전 치즈의 양을 C라고 하면 다시 꺼냈을 때 C//2로 줄어든다.
- 치즈가 모두 녹아 0이 되면 화덕에서 꺼내고, 바로 그 자리에 남은 피자를 순서대로 넣는다.

 

[입력]

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50
다음 줄부터 테스트 케이스의 첫 줄에 화덕의 크기 N과 피자 개수 M이 주어지고, 다음 줄에 M개의 피자에 뿌려진 치즈의 양을 나타내는 Ci가 주어진다.
3<=N<=20, N<=M<=100, 1<=Ci<=20

 

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 번호를 출력한다.

 

💡 풀이법

1. 피자의 번호를 출력해야 하기 때문에 피자의 번호와 함께 치즈를 같이 저장한다.

2. 화덕보다 피자의 양이 더 많기 때문에 처음에 화덕에 들어갈 수 있는 피자와 남는 피자로 나눈다.

3. 화덕의 피자를 앞에서 하나씩 보며 치즈의 반이 0이 아니면 리스트의 뒤로 추가한다.

4. 만약 치즈의 반이 0이라면 그 피자를 pop하고 남은 피자중 가장 앞에 있는 피자를 화덕에 추가해준다.

5. 그렇게 돌리다가 화덕에 피자가 1개만 남게되면 while문을 종료한다.

6. 화덕에 있는 단 하나의 피자가 결국 마지막까지 남게 된 피자이므로 피자의 인덱스를 출력한다.

 

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    pizza_list = list(map(int, input().split())) # pizza 리스트
    pizza = [[i+1, p] for i, p in enumerate(pizza_list)]  # 각 피자의 인덱스와 치즈를 같이 저장
    fire = pizza[:N]  # 처음 화덕에 들어갈 수 있는 피자
    remain = pizza[N:]  # 못 들어가고 남는 피자

    while len(fire) > 1:
        cheese = fire.pop(0)
        if cheese[1]//2 != 0:
            cheese[1] = cheese[1]//2
            fire.append(cheese)
        else:
            if remain:
                fire.append(remain.pop(0))
    print('#{} {}'.format(tc, fire[0][0]))