[인프런] 퇴사

---

문제설명

저번에 다이나믹 프로그래밍으로 풀어본 퇴사 문제이다. 이번에 브루트포스(완전탐색)인 DFS를 활용해 해당 문제를 풀어보자.

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

14501번: 퇴사

사고과정

• 스스로 풀 때 상태트리를 만드려고 하는데, 여러갈래 길로 만들었다.. 1일차를 상담할때, 2일차를 상담할때,, 이런식으로..애써 구현은 했는데, 테스트 케이스 일부가 틀려서 구현 실패했다..
• 강의를 보니 두 갈래길로 상태트리를 만들어야 했다. 1일차 상담을 했는지 안했는지로, 만약 했다면 1일차 상담 하는 데 걸린 시간 이후의 k일차의 상담으로 이동해서 탐색한다. 만약 1일차 상담하지 않았다면 그냥 1일차에서 하루 증가시킨 2일차 상담을 하면 된다..
• 이 아이디어만 듣고 코드로 구현하니 생각보다 쉽게 구현이 가능했다.. 역시 초반 아이디어부터 잘못되었었다..
• 그리고 문제에서 N+1번째 날에 퇴사를 한다고 했으므로 상태트리의 레벨(L)값이 N+1이 되었을 때, 결과를 갱신한다. 단, L을 계산했을 때, N+1보다 크게 되면 그 때의 경로는 탐색하지 않고 해당 일차 상담을 하지 않는 경로로 간다!
• 아이디어만 듣고 구현한 풀이와 강의 속 풀이와 간결적인 측면에서 또 차이가 존재했었다..

풀이(스스로 못 푼 풀이)

- 나의 풀이

n = int(input())
t = [1]
p = [0]
answer = -2147000000
for _ in range(n):
    time, price = map(int, input().split())
    t.append(time)
    p.append(price)

def dfs(L, price):
    global answer
    if L == n+1:
        if price > answer:
            answer = price
        return
    if L > n+1:
        return
    else:
        dfs(L+t[L], price+p[L])
        dfs(L+1, price)

dfs(L=1, price=0)   # 일자, 실시간 누적 금액
print(answer)

- 강사님 풀이

n = int(input())
T = list()
P = list()
for i in range(n):
    a, b = map(int, input().split())
    T.append(a)
    P.append(b)
res = -2147000000
T.insert(0, 0)
P.insert(0, 0)


def DFS(L, sum):
    global res
    if L == n+1:
        if sum > res:
            res = sum
    else:
        # 현재 날짜 + 현재 날짜의 상담 완료 시간이 N+1일 이하일 경우에만 더 진행!
        if L + T[L] <= n+1:
            DFS(L+T[L], sum+P[L])
        DFS(L+1, sum)


DFS(1, 0)
print(res)