백준 15235번 [Olympiad Pizza](C++) -yes6686- 티스토리

백준 문제 풀이: 15235 (Olympiad Pizza)

---

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

문제 설명:

n명의 학생들이 원형으로 앉아 있고, 각자가 먹어야 할 피자 조각 수가 주어진다. 피자는 한 번에 한 조각씩 나눠지며, 첫 번째 학생부터 시작해 한 바퀴씩 순차적으로 1조각씩 나누어준다. 피자를 받은 학생은 남은 조각 수를 1 줄이며, 만약 0이 되면 더 이상 받지 않는다.

모든 학생이 자신의 피자를 다 먹을 때까지 이 과정을 반복하며, 각 학생이 마지막으로 피자를 받은 시점을 구해야 한다.

---

문제 해결 코드

// 15235번: Olympiad Pizza
// 원형 순회하며 각 학생이 피자 다 먹는 마지막 시점 기록

#include <iostream>
using namespace std;

int arr[1001];  // 각 학생이 필요한 피자 조각 수
int cnt[1001];  // 각 학생이 마지막으로 피자 받은 시점

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int time = 0;  // 현재 시간 (피자 조각 수 기준)
    while (true) {
        bool done = true;

        for (int i = 0; i < n; i++) {
            if (arr[i] > 0) {
                done = false;
                time++;
                arr[i]--;        // 피자 한 조각 먹기
                if (arr[i] == 0)
                    cnt[i] = time;  // 마지막 조각 시간 기록
            }
        }

        if (done) break;  // 모두 다 먹었으면 종료
    }

    for (int i = 0; i < n; i++) {
        cout << cnt[i] << ' ';
    }
}

---

코드 설명

• 핵심 알고리즘: 시뮬레이션 — 순차적으로 한 명씩 피자 한 조각씩 배분
• 구현 세부사항:
  • arr[i]: i번째 학생이 남은 피자 조각 수
  • cnt[i]: i번째 학생이 마지막 피자를 받은 시간
  • 매 시간마다 순회하며 조각이 남은 학생에게만 1조각 배분
• 시간 복잡도 분석:

  O(n ⋅ max(arr[i])) — 모든 조각이 나눠질 때까지 순차 순회

---

결과

각 학생이 마지막으로 피자를 받은 시간을 출력합니다.

예시 입력:
3
2 1 3

예시 출력:
4 2 6

설명: - 1라운드: 1번(1), 2번(1), 3번(1) → 1 0 2 - 2라운드: 1번(0), 3번(1) → 0 0 1 - 3라운드: 3번(0)

다른 접근 방식이나 개선 아이디어가 있다면 댓글로 자유롭게 남겨주세요!