문제

' 3985번 롤 케이크 '
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)
• 첫째 줄에는 가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호를, 둘째 줄에는 실제로 가장 많은 조각을 받은 방청객의 번호를 출력한다. 단, 여러 명인 경우에는 번호가 작은 사람을 출력한다.

풀이 순서

• L, N, P, K 입력값을 받는다.
• 가장 많은 조각을 받는 예상 방청객 번호는 불린 수 P와 K의 차이로만 비교하여 가장 큰 값을 출력한다.
• L까지 배열을 만들어서 실제로 받을 수 있는 범위를 체크한다. 단, 이미 불린 번호는 다음 사람이 받지 못하도록 한다.
• 배열의 순회하면서 가장 많이 받는 인덱스 번호를 출력한다.

코드

Python

L = int(input())
N = int(input())
arr = [0 for _ in range(L + 1)]  # L : (1 ≤ L ≤ 1000)
mx = 0  # 가장 많은 조각을 받을 예상 방청객 번호
mx_i = 0
for n in range(N):
    P, K = map(int, input().split())
    if K - P > mx:  # 여러명인 경우 번호가 작은 사람을 출력하도록 초과 범위 지정
        mx_i = n + 1
        mx = K - P
    for i in range(P, K + 1):
        if arr[i] == 0:  # 이미 번호 적혀있으면 받지 못함
            arr[i] = n + 1
print(mx_i)  # 가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호를 출력
real = 0
real_i = 0  # 실제로 많이 받는 방청객 번호
for i in range(1, N + 1):
    x = arr.count(i)
    if x > real:
        real = x
        real_i = i
print(real_i)  # 실제로 가장 많은 조각을 받은 방청객의 번호를 출력

다른 방법

L=int(input())
arr=[0 for _ in range(L+1)]
N=int(input())
pred_i=0
pred_cnt =0
for i in range(1,N+1):
    P,K = map(int, input().split())
    #[P,K]범위에 방청객 i를 표기...
    for j in range(P,K+1):
        #이미 표기가 되어 있다면 넘어가고 표기안된 부분만 표시 가능
        if arr[j] != 0:
            arr[j] = i  # 해당 방청객 번호 표시
    if pred_cnt < K-P :
        pred_cnt = K-P
        pred_i = i
        
mx_cnt=0
mx_i=0
for i in range(1,N+1):
    #롤 케이크를 모두 순회해서 해당 방청객 i에 대한 카운트를 확인
    cnt = arr.count(i)
    if mx_cnt < cnt:
        mx_cnt = cnt
        mx_i = i

print(mx_i)