[백준] 14501 퇴사 python3

문제 : https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

코드

N = int(input())
T = [0] * (N+1)
P = [0] * (N+1)

for i in range(1, N+1):
    T[i], P[i] = map(int, input().split(" "))

# 격자 만들기
grid = [[0]*(N+1) for _ in range(N+1)] # row: 상담, column: 일

# 격자 채우기
for row in range(1, N+1):
    time = T[row]
    price = P[row]
    for col in range(1, N+1):
        previous = max(grid[row-1][col], grid[row][col-1])
        if row+time-1 == col:
            grid[row][col] = max(previous, price + grid[row-1][col-time])
        else:
            grid[row][col] = previous

print(grid[N][N])

 

해설

1일차 상담을 시작한다고 하면, T1=3 이므로 3일째에 상담이 끝나게 된다.

2일차 상담을 시작한다고 하면, T2=5 이므로 6일째에 상담이 끝나게 된다. 

 

그림1. 백준이에게 잡힌 상담에 소요되는 날들

 

동적 프로그래밍을 활용하여 문제를 풀기 위해 격자를 그려보기로 했다.

격자를 그리기 위해 고려해야 할 것은 다음과 같다.

1. 각 Cell에 넣을 값 (최적화 시키고자 하는 값)은 무엇인가? -> 최대 price
2. 이 문제를 어떻게 하위 문제로 나눌 수 있는가? -> n-1, n-2...개의 상담이 있을 때 최대 price
3. 격자의 축은 무엇인가? -> 각 상담과 날짜

그림2. 격자

문제의 제약 조건은 다음과 같다.

1. 그림1에서의 상담 날짜가 겹치면 안된다. = 상담이 끝난 다음날에 새로운 상담을 할 수 있다.
2. 어떠한 상담이든 지정된 날짜 (ex: 3일차의 상담은 3일)에만 시작할 수 있다.

상담이 끝난 다음날에 새로운 상담을 시작할 수 있으므로, 상담이 끝난 날을 기준으로 셀을 채울 수 있다.

 

상담 A, B만 있을 때 채운 격자

상담 B는 6일째에 끝나기에 2행 6열에 들어갈 수 있다. 그리고 상담 A와 B는 동시에 할 수 없으므로 (기간이 겹침) 둘 중 price가 높은 상담을 선택해서 cell을 채운다.

 

상담 A,B,C,D 에서의 격자

상담 D에 대하여 T4=1, P4=20 이며, 상담 D는 4일째에 시작해서 4일째에 끝난다. 따라서 3일째에 끝나는 A와 같이 상담할 수 있다. 즉, [4일째 - 1일]에서의 최댓값 + 상담 D의 price 를 가질 수 있으며, 이를 수식으로 나타내면 P4 + grid[ i-1 ][ j-T4] 이다.

 

이를 일반화시켜 격자를 채워보면 다음과 같이 나온다.

그림3. 채워진 격자

 

우리는 상담G까지 있을 때 7일째의 최댓값을 찾고자하므로, grid[7][7]의 값을 출력하면 된다.