[백준 - 14501] 퇴사

문제

문제링크
퇴사를 N+1일째 할 예정인데 그 동안에 가장 금액이 높을 수 있도록 일을 하고싶다. 얻을 수 있는 최대 수익은 얼마인가?

문제 풀이

처음에는 해당 날짜에 상담을 받는가 안받는가로 나누어서 이중배열을 활용하여 풀려고 했다.
하지만 좀 더 생각해보니 해당 날짜에서 상담을 받는 경우만 생각하여 T[i]의 날짜 뒤로 받은 금액을 모두 업데이트 해주면 간단하게 풀린다는 것을 깨달았다.

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())

array = [0] * 21
def solution():
    global T, P, n
    for i in range(1, n+1):
        # T는 기간 P는 돈
        temp = array[i] + P[i]
        # 금액을 얻는 날짜 이후로 업데이트
        for j in range(i+T[i], 21):
            if array[j] < temp : # 지금까지의 최고 금액과 비교해서 넣기
                array[j] = temp
    return array[n+1]

print(solution())

답안
dp[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익
dp[i] = max(p[i] + dp[t[i]+i], max_value)
로 계산하여 정의했다.

n = int(input()) # 전체 상담 개수
t = [] # 각 상담을 완료하는 데 걸리는 시간
p = [] # 각 상담을 완료했을 때 받을 수 있는 금액
dp = [0] * (n + 1) # 다이나믹 프로그래밍을 위한 1차원 dp 테이블 초기화
max_value = 0

for _ in range(n):
    x, y = map(int, input().split())
    t.append(x)
    p.append(y)

# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n -1, -1, -1):
    time = t[i] + i
    # 상담이 기간 안에 끝나는 경우
    if time <= n:
        # 점화식에 맞게, 현재까지의 최고 이익 계산
        dp[i] = max(p[i] + dp[time], max_value)
        max_value = dp[i]

    # 상담이 기간을 벗어나는 경우
    else :
        dp[i] = max_value

print(max_value)

똑같은 메모리/시간을 활용하는 것을 볼 수 있으나, 일반적인 DP의 형태로 문제를 푸는 연습을 위해서는 답안과 같은 방식이 좋을 것이라 생각한다.

개선할 점

너무 어렵게 생각하지 말고 직접 손으로 풀어보는 것이 중요하다! 또한 DP 감각을 잃지말자.

해당 문서는 '이것이 코딩 테스트다. with 파이썬 - 나동빈 저'를 읽고 정리한 내용입니다.