백준 3985번 롤 케이크 파이썬

리뷰

문제가 잘 이해가 되지 않는다면 예제의 이미지를 보면 쉽게 접근할 수 있는 문제였다.

문제 풀이

입력값을 받아오고 롤케이크 길이 +1만큼의 배열을 생성해준다. (롤케이크의 길이가 1부터 시작이기 때문)

가장 많은 조각을 받을 것으로 기대했던 방청객과 실제로 가장 많은 조각을 받은 방청객용 변수를 따로 초기화 해준다.

이 때 값 비교용 변수 하나 방청객의 인덱스용 변수 하나를 각각 초기화 해주었다.

 

for문을 1부터 시작하여 i를 방청객 인덱스로 활용해 주고 k - p값이 이전의 값들 보다 클 경우 i 값은 가장 많은 조각을 받으로 기대했던 방청객의 인덱스가 된다. (방청객 인덱스는 오름차순 이므로 자동으로 번호가 가장 작은 값이 할당된다.)

 

이후 for문을 한번 더 개행해 줘 롤케이크에 방청객 번호가 할당되지 않을 경우 현재 방청객 번호를 할당해 주고, 몇번 할당 되었는지를 cnt 변수로 체크하여 기존 값 보다 클 경우 실제로 가장 많은 조각을 받은 방청객의 인덱스를 최신화 해줬다.

참고 사항

문제가 잘 이해가 되지 않는다면 예제의 이미지를 참고하자

정답 코드

def q3985():
    # 백준 3985번 롤 케이크 파이썬
    l = int(input())
    n = int(input())
    dp = [0] * (l + 1)
    large1, index1, large2, index2 = 0, 0, 0, 0
    for i in range(1, n + 1):
        p, k = map(int, input().split())
        cnt = 0
        if k - p > large1:
            large1 = k - p
            index1 = i
        for j in range(p, k + 1):
            if not dp[j]:
                dp[j] = i
                cnt += 1
        if cnt > large2:
            large2 = cnt
            index2 = i
    print(index1)
    print(index2)
q3985()