BAEKJOON : 14501

No. 14501

1. Problem

2. My Solution

• Bottom up DP 알고리즘을 이용
• dp[0] 부터 끝까지 왼쪽에서부터 오른쪽 (정방향)으로 값을 구함 -> 실패
• 마지막 입력 예제에서 90이 아닌 110이 출력됨. dp[8] = 80 이후에 dp[10] 에서 8일에 일을 할 수 있다고 판단해 110으로 출력됨 (7일에 2일 상담하므로 8일은 불가능)

import sys

n = int(sys.stdin.readline())
T = [0]
P = [0]
dp = [0] * (n+1)

for _ in range(n):
    t,p = map(int, sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

for day in range(1,n+1):
    temp = 0
    if T[day] > 1:
        for i in range(day-1,-1,-1):    
            if T[i] == day-i+1:
                temp = dp[i] + P[i]
            dp[day] = max(dp[day], dp[day-1], temp)
    else:
        for i in range(day-1,-1,-1):
            if T[i] == day-i+1:
                temp = dp[i] + P[i]
            dp[day] = max(dp[day], dp[day-1] + P[day], temp)
    
print(dp[n])

3. Others' Solutions

• 첫 번째 방법
• Bottom up DP 방식은 동일하지만 오른쪽에서 왼쪽 (역방향)으로 진행

import sys

n = int(sys.stdin.readline())
T = [0]
P = [0]
dp = [0] * (n+1)

for _ in range(n):
    t,p = map(int, sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

# 초기값 설정
if T[n] == 1:
    dp[n] = P[n]

for day in range(n-1,0,-1):
   
    # day에 상담하면 퇴사일을 넘어가는 경우
    if day+T[day]-1 > n:
        dp[day] = dp[day+1]
    
    # day에 상담을 하는 경우와, 하지 않고 다음 day로 넘어가는 경우중 큰 값
    else:
        if day+T[day]-1 == n:      # day 기준으로 T[day]만큼 일하면 마지막 날인 경우
            work = 0
        else:
            work = dp[day+T[day]]
        dp[day] = max(dp[day+1], work + P[day])

print(dp[1])

• 두 번째 방법
• DFS 를 이용해 완전탐색 (return 이용 X)

import sys

def dfs(day,sum):
    global res
    flag = False

    if day+T[day]-1 <= n:           # 해당 day에 일을 해도 퇴사일을 넘지 않으므로 일을 하는 경우
        sum += P[day]               # 일을 했으니 돈을 받음
        flag = True

        if day+T[day] <= n:         # 그 뒤로 날이 남아있는 경우 
            dfs(day+T[day], sum)        
        
        res = max(res,sum)

    if flag == True:            # 일하는 경우를 dfs 로 체크했다면 안하는 경우를 위해 다시 -
        sum -= P[day]     

    if day+1 <= n:              # 해당 day에 일을 안하는 경우 
        dfs(day+1, sum)
    
    
n = int(sys.stdin.readline())
T = [0] 
P = [0]
res = 0

for _ in range(n):
    t,p = map(int,sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

dfs(1,0)
print(res)

• 세 번째 방법
• DFS 를 이용해 완전탐색 (return 이용)

import sys
import math

def dfs(day):
    
    # 정확히 마지막 날의 경우
    if day-1 == n:      
        return 0

    # 퇴사일을 넘어가는 경우
    elif day > n:
        return -math.inf
    
    # day를 기준으로 일을 하지 않고 바로 다음날로 가거나, 일을 하고 일한 날짜만큼 뒤로 가거나
    return max(dfs(day+1), dfs(day+T[day])+P[day])
    
    
n = int(sys.stdin.readline())
T = [0] 
P = [0]

for _ in range(n):
    t,p = map(int,sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

print(dfs(1))

• 네 번째 방법
• Top Down DP = DFS + 백트래킹

import sys
import math

def dfs(day):

    # 정확히 마지막 날의 경우
    if day-1 == n:      
        return 0

    # 퇴사일을 넘어가는 경우
    elif day > n:
        return -math.inf
    
    if dp[day] != -1:
        return dp[day]
    
    # day를 기준으로 일을 하지 않고 바로 다음날로 가거나, 일을 하고 일한 날짜만큼 뒤로 가거나
    dp[day] = max(dfs(day+1), dfs(day+T[day])+P[day])
    print(dfs(day+1), dfs(day+T[day])+P[day])
    return dp[day]
    
n = int(sys.stdin.readline())
T = [0] 
P = [0]
dp = [-1] * (n+1)

for _ in range(n):
    t,p = map(int,sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

print(dfs(1))

4. Learned

• bottom up 방식만을 쓰다보니 "DP 는 무조건 이전의 값(결과)을 이용하는 것이다" 라는 생각을 했던 것 같다. 기본적으로 재귀호출이 일어나고 중복된 부분을 제거하는 것이 dp라는 사실을 잊지말고 top down 방식도 번갈아 사용하자
• DP[i] 결과를 구할 때 정방향이 아닌 역방향도 가능하다
• 궁금한 건 못 참지