[백준/Python3] 3985번 롤 케이크

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

3985번: 롤 케이크

문제

인기 티비 프로그램 "나는 요리사 인가?"의 새 시즌이 시작한다. 이번 시즌은 기네스북에 등재될 만한 음식을 만드는 것을 목표로 진행한다.

첫 번째 에피소드에 출연하는 요리사는 전설의 요리사 김상근이고, 길이 L미터의 롤 케이크를 만들 것이다.

상근은 몇 시간동안 집중해서 케이크를 만들었고, 이제 스튜디오의 방청객 N명에게 케이크를 나누어 주려고 한다.

상근이는 롤 케이크를 펼쳐서 1미터 단위로 잘라 놓았다. 가장 왼쪽 조각이 1번, 오른쪽 조각이 L번 조각이다. 방청객은 1번부터 N번까지 번호가 매겨져 있다. 각 방청객은 종이에 자신이 원하는 조각을 적어서 낸다. 이때, 두 수 P와 K를 적어서 내며, P번 조각부터 K번 조각을 원한다는 뜻이다.

프로그램의 진행자 고창영은 1번 방청객의 종이부터 순서대로 펼쳐서 해당하는 조각에 그 사람의 번호를 적을 것이다. 이때, 이미 번호가 적혀있는 조각은 번호를 적지 못하고 넘어간다. 이런 방식을 이용해서 방청객에게 조각을 주다보니, 자신이 원래 원했던 조각을 받지 못하는 경우가 생길 수 있다.

아래 그림은 이 문제의 예제를 나타낸 것이다.

가장 많은 케이크 조각을 받을 것으로 기대한 방청객의 번호와 실제로 가장 많은 케이크 조각을 받는 방청객의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 롤 케이크의 길이 L (1 ≤ L ≤ 1000)이 주어진다. 둘째 줄에는 방청객의 수 N (1 ≤ N ≤ 1000)이 주어진다. 다음 N개 줄에는 각 방청객 i가 종이에 적어낸 수 Pi와 Ki가 주어진다. (1 ≤ Pi ≤ Ki ≤ L, i = 1..N)

출력

첫째 줄에 가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호를 출력한다.

둘째 줄에 실제로 가장 많은 조각을 받은 방청객의 번호를 출력한다.

각 경우에 조건을 만족하는 방청객이 두 명 이상이라면 그중 번호가 가장 작은 방청객의 번호를 출력한다.

 

 

<정답 코드>

L = int(input())
cake = [0] * (L + 1)
N = int(input())

want_pieces = 0
want_person = 0

for i in range(1, N + 1):
    p, k = map(int, input().split())
    if want_pieces < k - p:
        want_pieces = k - p
        want_person = i

    for j in range(p, k + 1):
        if cake[j] != 0:
            continue
        else:
            cake[j] = i

print(want_person)

max_pieces = 0
max_person = 0
for i in range(1, N + 1):
    if max_pieces < cake.count(i):
        max_person = i
        max_pieces = cake.count(i)

print(max_person)

<풀이>

제일 먼저 한 생각은 케이크 조각의 점유를 나타내자 라는 생각이었습니다.

따라서 케이크 조각의 수 L을 입력받고, cake 리스트를 L + 1의 크기의 리스트로 정했습니다.

이렇게 정한 이유는, 앞으로 나올 케이크 번호라든가, 사람의 번호라든가가 모두 1부터 시작하기 때문입니다.

 

이제 아래에서 want_person, want_pieces 변수를 선언해, 문제에 맞는 가장 많은 케이크 조각을 원하는 사람을 구하기 위해 선언해주었습니다.

이를 구하는 알고리즘은 각 사람에 대한 p, k를 입력받을 때마다 해당 구간(원하는 조각 수)의 크기가 가장 큰 것(want_pieces)과 k - p를 비교하여 만약 k - p가 기존 원했던 조각보다 많은 경우 want_pieces를 업데이트 하고 가장 많이 원한 사람(i)를 want_person으로 업데이트 시켜주는 것입니다. 

p, k를 입력받은 후, cake 리스트에서 각 사람의 번호를 원하는 조각 구간의 cake 리스트에 넣어주며 업데이트 시켰습니다. 

초기에 cake 리스트의 모든 elements가 0으로 초기화되어있기 때문에, 0이 아니라면 누군가 점유하고 있는 것이라, continue로 해당 구간은 건너 뛰게 되어, 점유되지 않은 (element == 0) 인 부분에만 다음 사람이 점유할 수 있도록 했습니다.

마지막으로 구한 것은 가장 많이 케이크 조각을 가져가게 되는 사람을 구하는 것인데,

아까 케이크 조각을 가장 많이 원했던 사람을 구하는 방법과 비슷합니다. 

이번에는 cake에서 i번째 사람이 점유한 조각을 count하면서, 기존에 가장 많았던 조각(max_pieces)를 cake.count(i) 가 넘어갈 경우 해당 사람과 해당 조각을 업데이트시켜 가장 많이 가져갈 사람을 구할 수 있도록 했습니다.