[백준] 14501 - 퇴사 (Python)

민영·2022년 3월 29일

백준 알고리즘

[Algorithm] 백준

목록 보기

19/31

문제

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

문제 설명

이 문제에서 잘 이해해야 되는 부분들이 있다.

1. 완료한 일에 대해 받아야 되는 돈은 완료한 날에 받는 것이 아니라 그 다음날에 받는다.
ex) 3일 걸리는 일을 1,2,3일동안 했으면 일을 완료한 3일에 바로 돈을 받는 것이 아니라 4일에 받는 것이다.
--> 즉, N일차까지 일을 해서 일을 완료했더라도 N+1일째 되는 날에는 퇴사를 했기 때문에 돈을 받을 수 없다는 뜻이다.

해당 문제 예제 4번을 보자.(5, 50) -> (4, 40) -> (1,10) 이렇게 실행하면 딱 10일 일하고 100을 받을 수 있을 것 같지만 정답은 90이다. 10일차에 일한 돈 10은 11일차에 받아야 되는데 11일차에는 퇴사를 했기 때문에 돈을 받을 수 없기 때문이다.

2. 일을 하는 날이 있고 안하는 날이 있다.
더 많은 돈을 벌기 위해 일부러 '일을 안하는 경우'와 일을 수행하다가 퇴사를 하기 때문에 '일을 못하는 경우'가 있다.

문제 설명 부분을 보면 이해할 수 있을 것이다.

이 부분을 잘 이해하고 이제 재귀함수를 만들어보자.

'i번째 날의 수익'은 다음날인 'i+1번째 날 수익'과 'i번째 날 수익' + 'T[i]만큼 지난 후 수익' 중 큰 값을 골라야 한다.

d[i] = Max(d[i+1], p[i]+d[i+t[i]])

제출 코드

N = int(input())
t = []
p = []
for i in range(N):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)

d = [0] * (N + 1)
for i in range(N - 1, -1, -1):
    if t[i] + i > N:
        d[i] = d[i + 1]
    else:
        d[i] = max(d[i + 1], p[i] + d[i + t[i]])

print(d[0])

결과

정리

개념

큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조 (Optimal Substructure)를 가졌다고 한다.
-> 동적 프로그래밍은 최적 부분 구조를 가지며 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생하는 문제의 해결에 적합한 기법이다.

대표적인 예시는 '피보나치 수'
f(n) = f(n-1) + f(n-2)
f(1) = f(2) = 1
즉, n의 피보나치 수는 n-1의 피보나치 수와 n-2의 피보나치 수를 포함하고 있고 f(n)은 f(n-1)과 f(n-2)를 재귀적으로 호출한다.

주석있는 코드

# 입력받기
N = int(input())
t = []
p = []
for i in range(N):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)

# 1차원 배열 N+1개 요소를 모두 0으로 초기화 
# (i번째에 i+1번째와 비교하니까 1 크게 선언)
d = [0] * (N + 1)

# range(start, end, step)
# 즉, i는 N-1부터 0까지 -1씩 하면서 for문을 도는 것이다
for i in range(N - 1, -1, -1):
    # '현재 일자 + 상담을 완료하는데 걸리는 기간 t'이 N을 넘어가면 일을 맡을 수 없다
    if i + t[i] > N:
        # 따라서 아래처럼 max로 비교할 필요없다
        d[i] = d[i + 1]
    else:
        # 'i번째 날의 수익'은 다음날인 'i+1번째 날 수익'과 'i번째 날 수익' + 'T[i]만큼 지난 후 수익' 중
        # 큰 값을 골라야 한다.
        d[i] = max(d[i + 1], p[i] + d[i + t[i]])

print(d[0])