백준 14501) 퇴사 (실버.3)

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

14501번: 퇴사

 

 

먼저 문제의 조건을 확인해보자. 

1) 직업이 상담사인 사람이 n+1일 째에 퇴사를 한다. 

2) 각각의 상담에는 개별의 시간이 걸리기 때문에 다음 상담은 이전 상담이 끝나고 나서 진행할 수 있다. 

3) 퇴사날 까지 일을 수행할 때 상담사가 벌 수 있는 최대 이익을 구한다. 

 

 

 

먼저 제일 먼저 생각했던 방법은 dfs를 이용해서 상담이 가능한 모든 경우의 수를 구하고 최대 이익을 구하는 방법이었다. 만약 첫번째 상담을 하기로 했으면 그 다음 상담이 가능한 경우는 첫번째 상담일 수가 지난 후일 것이기 때문에 범위는 range(idx, n)으로 구현하였다. 

여기서 맨 처음 값을 넣을 때, 만약 상담이 불가능하다면(상담을 하는데 퇴사날 보다 오래걸리는 경우) 원래 값 대신 0, 0을 넣어주었다. 

구현한 코드는 다음과 같다. 

global answer, n, consulting
n = int(input())
consulting = []
for i in range(n):
    a, b = map(int, input().split())
    if i+a >n : 
        consulting.append((0, 0))
        continue
    consulting.append((a, b))
answer = 0

def dfs(idx, pay):
    global n, answer
    answer = max(answer, pay)
    for i in range(idx, n):
        if consulting[i] == (0, 0) :
            continue
        if consulting[i][0]+idx <= n :
            dfs(i+consulting[i][0], pay + consulting[i][1])
dfs(0, 0)
print(answer)

 

그런데 문제를 풀고 생각해보니 이 문제는 동적 계획법으로도 값을 구할 수 있는 문제였다. 

 

불가능 한 경우에 이미 (소요시간:0, 상담비용:0)이라는 값을 넣어두었기 때문에, n번째 상담에서 가능한 최대 이익은 n번째 상담이익 + n+소요시간번째 상담에서 얻을 수 있는 최대이익이라는 것을 알수 있다. 

따라서 맨 처음 dp에 해당 인덱스에 해당인덱스번 상담을 해서 얻을 수 있는 값을 모두 넣어놓고 시간을 거슬러 가면서 answer[n] =  answer[n] + max(answer[n+consulting[n](소요날짜):])식을 이용하여 문제를 해결할 수 있었다. 

훨씬 직관적이고 간단한 구현이 가능하였다. 

global answer, n, consulting
n = int(input())
consulting = []
answer = [0]*n
for i in range(n):
    a, b = map(int, input().split())
    if i+a >n : 
        consulting.append((0, 0))
        continue
    consulting.append((a, b))
    answer[i] = b

for i in range(n-2, -1, -1):
    if i + consulting[i][0] == n : 
        continue
    answer[i] += max(answer[i+consulting[i][0]:])

print(max(answer))