boj14501 - 퇴사

5283 단어 코테코테

문제: 퇴사

당일에 일을 하냐 / 안하냐로 나누어
일을 하면 그 업무를 하는 시간과 비용을 더해 매개변수로 넘겨주고
일을 안하면 시간+1(다음날), 비용은 그대로 넘겨줌

dp로도 가능,,

import sys
answer =0 
def dfs(tp, N, day, tmp_cost):
    # 종료조건
    if day == N:
        global answer
        answer = max(tmp_cost, answer)
        # print(answer)
        return 

    # day에 일하는 경우
    if day + tp[day][0] <= N:
        dfs(tp, N, day + tp[day][0], tmp_cost + tp[day][1])

    # day에 일 안하는 경우 그냥 다음날로 넘어감
    if day + 1 <= N:
        dfs(tp, N, day+1, tmp_cost)


if __name__ == '__main__':
    input = sys.stdin.readline

    N = int(input())
    tp = []
    for i in range(N):
        t, p = map(int, input().split())
        tp.append([t,p])
    
    dfs(tp, N ,0, 0)
    print(answer)

참조: 풀이법

좋은 웹페이지 즐겨찾기