[BOJ] 14501. 퇴사

문제

퇴사 (https://www.acmicpc.net/problem/14501)

풀이

1. 초기 접근

• 문제조건 해석
  • 이 문제, 뭔가 어렵지 않아보이긴 하다.
  • 목표 상태(n 번째 일)가 있고, 상태에 도달하는 경로들을 탐색해나가야 한다.
    • 각 경로에 따라, 최종 상태의 값이 달라진다.
    • n도 매우 작다. DFS 로 풀 수 있다.
  • 한편, 점화식을 잘 세우면 DP로도 풀 수 있을 듯 하다.
• 알고리즘
  • DFS로 풀면, 다음과 같다.
  • 오늘이 i 일이라고 하자. 경우는 2가지다. 오늘 일할 경우와 일 안할 경우다.
  • 일 하면 i + t[i] 일에 또 위 선택을 해야한다.
    일 안하면 그냥 다음 날 i+1 일에 위 선택을 하면 다시 하면 된다.
  • 많아봐야 15일 까지니, 시간 복잡도는 O(2^15) 이다.
• 코드

def dfs(i, sum):
    # dfs 종료 조건. 현재 n+1일이 된 경우.
    if i == n+1:
        global answer
        answer = max(answer, sum)
        return

    if i+t[i] <= n+1:
        # 이 날(i번째 날) 일을 하는 경우.
        dfs(i + t[i], sum + p[i])
    if i+1 <= n+1:
        # 이 날(i번째 날) 일을 안하는 경우,
        # 다음 날로 넘어간다.
        dfs(i + 1, sum)

n = int(input())
t, p = [0], [0]
for _ in range(n):
    ti, pi = list(map(int, input().split()))
    t.append(ti)
    p.append(pi)

answer = 0
dfs(1, 0)
print(answer)

다른 풀이

• DFS 말고, DP로 푸는 법 역시 있었다.
• 아래 코드가 제일 직관적이고 깔쌈하게 풀어서, 링크 해논다.

끄적끄적님 블로그

https://private-space.tistory.com/14

여담

• 처음에 DP 로 접근했다가, 식이 잘 안나와서 우왕좌왕 엄청 헤맸다.
  • D[i] 를 i일 까지 번 최대 수입이라고 두고, 이리저리 뭔가를 해봤다.
  • 안된다.
  • 끄적끄적님 블로그에 사이다 같은 코드가 있다. 핵 시원.
• 세상에서 제일 화나는 때는, 쉬워보이는 문제 제대로 안풀릴 때다.