[BaekJoon] 백준 3985 롤 케이크 (Python / 파이썬)

BaekJoon 백준 3985 롤 케이크 문제는 방청객은 종이에 자신이 원하는 롤케이크의 조각을 적어서 낸다. 가장 많은 케이크 조각을 받을 것으로 기대한 방청객의 번호와 실제로 가장 많은 케이크 조각을 받는 방청객의 번호를 구하는 문제이다. 난이도는 Bronze 1이다.

 

BaekJoon 3985 롤 케이크 문제 정보

출처

- https://www.acmicpc.net/problem/3985

난이도

- 브론즈 1 / Bronze 1

 

롤 케이크 문제 요약

• 길이 L미터의 롤 케이크를 방청객 N명에게 나누어 주려고 한다.  (1 ≤ L ≤ 1000, 1 ≤ N ≤ 1000)
• 롤 케이크를 펼쳐서 1미터 단위로 잘라 놓았다. 가장 왼쪽 조각이 1번, 오른쪽 조각이 L번 조각이다.
• 방청객은 1번부터 N번까지 번호가 매겨져 있다. 각 방청객은 종이에 자신이 원하는 조각을 적어서 낸다. 이때, 두 수 P와 K를 적어서 내며, P번 조각부터 K번 조각을 원한다는 뜻이다. (1 ≤ Pi ≤ Ki ≤ L, i = 1.. N)
• 1번 방청객의 종이부터 순서대로 펼쳐서 해당하는 조각에 그 사람의 번호를 적을 것이다. 이때, 이미 번호가 적혀있는 조각은 번호를 적지 못하고 넘어간다.
• 이런 방식을 이용해서 방청객에게 조각을 주다 보니, 자신이 원래 원했던 조각을 받지 못하는 경우가 생길 수 있다.
• 가장 많은 케이크 조각을 받을 것으로 기대한 방청객의 번호와 실제로 가장 많은 케이크 조각을 받는 방청객의 번호를 구하여 출력한다.
• 가장 많은 조각을 받도록 예상되는 방청객이 여러 명인 경우에는 번호가 작은 사람을 출력한다.

 

문제 풀이 과정

1. i 번 방청객의 원하는 조각을 저장한다.
2. 가장 많은 조각을 원하는 방청객인지 판별하고, 맞다면 i를 저장한다.
3. 원하는 번호의 범위 내의 롤케이크가 남아있다면 번호를 적고 카운트한다.
4. 카운트 한 만큼이 실제로 받을 수 있는 조각 수 이므로 저장한다.
5. 방청객의 수만큼 1~4번 과정을 반복한다.
6. 가장 많은 케이크 조각을 받을 것으로 기대한 방청객의 번호와 실제로 가장 많은 케이크 조각을 받는 방청객의 번호를 출력한다.

 

코드 및 설명

• rollCake - 롤케이크의 L번 조각에 받을 방청객의 번호가 적힌 리스트
• received - i번 방청객의 실제로 받을 조각 개수가 저장된 리스트
• maxPieces - 현재까지 가장 많은 케이크 조각을 받을 것으로 기대되는 조각 수
• wantMaxNum - 가장 많은 케이크 조각을 받을 것으로 기대한 방청객의 번호

L = int(input())
N = int(input())

rollCake = [0] * (L + 1)
received = [0] * (N + 1)
maxPieces, wantMaxNum = 0, 0

for i in range(1, N + 1):
    cnt = 0
    P, K = map(int, input().split())

    # 가장 많은 조각을 받을 것으로 기대한 방청객 번호
    wantPieces = K - P
    if maxPieces < wantPieces:
        maxPieces = wantPieces
        wantMaxNum = i

    # 해당 번호의 롤케이크 있으면 제공
    for j in range(P, K + 1):
        if rollCake[j] == 0:
            rollCake[j] = i
            cnt += 1
    received[i] = cnt

print(wantMaxNum)
print(received.index(max(received)))

---

BaekJoon 백준 3985 롤 케이크 문제를 파이썬 python으로 풀어보았다. 난이도는 Bronze 브론즈 1이다.