문제
인기 티비 프로그램 "나는 요리사 인가?"의 새 시즌이 시작한다.
이번 시즌은 기네스북에 등재될 만한 음식을 만드는 것을 목표로 진행한다.
첫 번째 에피소드에 출연하는 요리사는 전설의 요리사 김상근이고, 길이 L미터의 롤 케이크를 만들 것이다.
상근은 몇 시간동안 집중해서 케이크를 만들었고, 이제 스튜디오의 방청객 N명에게 케이크를 나누어 주려고 한다.
상근이는 롤 케이크를 펼쳐서 1미터 단위로 잘라 놓았다.
가장 왼쪽 조각이 1번, 오른쪽 조각이 L번 조각이다. 방청객은 1번부터 N번까지 번호가 매겨져 있다.
각 방청객은 종이에 자신이 원하는 조각을 적어서 낸다.
이때, 두 수 P와 K를 적어서 내며, P번 조각부터 K번 조각을 원한다는 뜻이다.
프로그램의 진행자 고창영은 1번 방청객의 종이부터 순서대로 펼쳐서 해당하는 조각에 그 사람의 번호를 적을 것이다.
이때, 이미 번호가 적혀있는 조각은 번호를 적지 못하고 넘어간다.
이런 방식을 이용해서 방청객에게 조각을 주다보니, 자신이 원래 원했던 조각을 받지 못하는 경우가 생길 수 있다.
아래 그림은 이 문제의 예제를 나타낸 것이다.
가장 많은 케이크 조각을 받을 것으로 기대한 방청객의 번호와 실제로 가장 많은 케이크 조각을 받는 방청객의 번호를 구하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/3985
입력
첫째 줄에 롤 케이크의 길이 L (1 ≤ L ≤ 1000)이 주어진다.
둘째 줄에는 방청객의 수 N (1 ≤ N ≤ 1000)이 주어진다.
다음 N개 줄에는 각 방청객 i가 종이에 적어낸 수 Pi와 Ki가 주어진다. (1 ≤ Pi ≤ Ki ≤ L, i = 1..N)
출력
첫째 줄에 가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호를 출력한다.
둘째 줄에 실제로 가장 많은 조각을 받은 방청객의 번호를 출력한다.
각 경우에 조건을 만족하는 방청객이 두 명 이상이라면 그중 번호가 가장 작은 방청객의 번호를 출력한다.
예제
# input
10
3
2 4
7 8
6 9
# output
3
1
# input
10
3
1 3
5 7
8 9
# output
1
1문제 풀이
import sys
input = sys.stdin.readline
# 입력 받기
L = int(input())
N = int(input())
# 케이크 배열 초기화
cake_distribution = [0] * (L + 1)
# 예상 최대 길이와 사람 변수 초기화
max_expected_length, max_expected_person = 0, 0
# 실제 케이크 조각 수령 개수 딕셔너리 초기화
cake_count = {}
for i in range(1, N + 1):
P, K = map(int, input().split())
# 최대 요청 구간 길이와 그 사람 찾기
requested_length = K - P + 1
if requested_length > max_expected_length:
max_expected_length = requested_length
max_expected_person = i
cake_count[i] = 0
# 실제 케이크 배정
for j in range(P, K + 1):
if cake_distribution[j] == 0:
cake_distribution[j] = i
cake_count[i] += 1
# 최대 요청 구간 길이를 요청한 사람 출력
print(max_expected_person)
# 실제로 가장 많은 케이크 조각을 차지한 사람 출력
print(max(cake_count, key=cake_count.get))파이썬을 독학하시는 분들에게 도움이 되길 바라며,
혹 더 좋은 방법이 있거나 오류가 있다면 편하게 말씀 부탁드립니다.
