[백준 15235번] Olympiad Pizza (C++)

문제링크 : https://www.acmicpc.net/problem/15235

15235번: Olympiad Pizza

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[1001];
vector<int>result;
queue<int>q;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    cin >> N;
    result.resize(N);
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
        q.push(i);
    }

    int t = 1; //걸리는 시간
    while(!q.empty())
    {
        int cur = q.front(); q.pop(); //현재 인덱스(위치)
        if(--arr[cur]==0) result[cur] = t; //걸린 시간 저장
        else q.push(cur);
        t++; //시간 증가
    }

    for(int i=0; i<N; i++)
    {
        cout << result[i] << " ";
    }
    return 0;
}

지문이 영어이지만 실버 5인 만큼 어렵지 않은 문제이다.

 

시간을 하나씩 증가시켜줌과 동시에 현재 값을 1개 줄여준다. (1개 나눠준 상태)

만약 현재 값이 1개 줄임으로써 0이 된다면 전부 나눠준 것이므로 걸린 시간을 저장해주고 아니라면 다시 큐에 넣어준다.

한 번의 피자 나눔이 지나갔으므로 시간이 1개 늘어나고 위의 과정을 큐에 값이 없어질때까지 반복해준다.

 

<예제 1 3 1 4>
t=1 : 0 3 1 4 -> 1번 인덱스 걸린시간 1
t=2 : 0 2 1 4
t=3 : 0 2 0 4 -> 3번 인덱스 걸린시간 3
t=4 : 0 2 0 3
t=5 : 0 1 0 3
t=6 : 0 1 0 2
t=7 : 0 0 0 2 -> 2번 인덱스 걸린시간 7
t=8 : 0 0 0 1
t=9 : 0 0 0 0 -> 4번 인덱스 걸린시간 9