알고리즘/BOJ

[BOJ] 14501 - 퇴사

서노리 2022. 2. 14. 21:43
반응형

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

 

14501번: 퇴사

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

www.acmicpc.net

n = int(input())
data = []

for i in range(n):
    time, benefit = map(int, input().rstrip().split())
    data.append((time, benefit))

dp = [0] * (n + 1)
max_value = 0
for i in range(n - 1, -1, -1):
    if i + data[i][0] <= n:
        dp[i] = max(dp[i + data[i][0]] + data[i][1], max_value)
        max_value = dp[i]

    else:
        dp[i] = max_value

print(max_value)

이 문제는 뒤쪽 날짜부터 거꾸로 확인하면서 DP 테이블을 갱신해나가는 다이나믹 프로그래밍 아이디어로 풀 수 있다.

문제의 예를 통해 보면 1일차에 상담을 진행하는 경우 최대 이익은 '1일차의 상담 금액 + 4일차부터의 최대 상담 금액'이 된다. 이러한 원리를 이용하여 뒤쪽 날짜부터 거꾸로 계산하며 문제를 해결할 수 있다.

 

'dp[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익'이라고 하면 코드로는 다음과 같이 나타낼 수 있다.

dp[i] = max(dp[i + data[i][0]] + data[i][1], max_value)

 

느낀 점

뒤쪽 날짜부터 확인한다는 아이디어를 떠올리는 것이 쉽지 않았다. 따라서 또 다른 방법으로 풀 수 있을까 하여 다른 블로그들을 많이 찾아본 결과 문제에서 N의 범위가 15밖에 안돼서 완전 탐색으로도 문제를 풀 수 있다는 점을 알고 완전 탐색으로도 다시 풀어보았다.

 

n = int(input())
data = []

for i in range(n):
    time, benefit = map(int, input().rstrip().split())
    data.append((time, benefit))

max_value = 0
dp = [0] * n
for i in range(n):
    if data[i][0] + i > n:
        continue
    dp[i] = data[i][1]

    for j in range(i):
        if data[j][0] + j > i:
            continue
        dp[i] = max(dp[i], data[i][1] + dp[j])

    max_value = max(max_value, dp[i])

print(max_value)

 

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 12015 - 가장 긴 증가하는 부분 수열 2  (0) 2022.02.15
[BOJ] 18353 - 병사 배치하기  (0) 2022.02.14
[BOJ] 2110 - 공유기 설치  (0) 2022.02.06
[BOJ] 1654 - 랜선 자르기  (0) 2022.02.02
[BOJ] 2108 - 통계학  (0) 2022.01.28