<aside> 🔥 백준 14501 문제 링크

</aside>

<aside> 🔥 문제 정리

n은 퇴사까지 남은 기간이고, t는 상담에 걸리는 일 수, p는 해당 상담을 마치면 버는 금액이다.

최대 수익을 구하는 프로그램을 짜보자.

첫째 줄에 n이 주어진다.

n개의 줄에 t와 p가 주어진다.

# 입력값
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

# 출력값
45

위 예시의 경우 1일 4일 5일에 일을 하는 것으로 10 + 20 + 15로 45이다.

</aside>

<aside> 🔥 접근 방법

이 문제도 역시 해결하지 못했다.

풀이에서의 접근 방법을 보면, 누적값으로 비용과 날짜를 재귀적으로 호출해서

근무를 할떄와 안할때의 모든 경우의수를 돌아서 최대값을 계속해서 갱신해서

최대값을 찾는 방식으로 코드를 구성했다.

아래 그림과 같은 방식으로 상당히 깊게 들어가서 모든 경우의 수를 파악한다.

</aside>

<aside> 🔥 코드

import sys

with open('퇴사.text') as f:
    sys.stdin = f
    input = sys.stdin.readline

    # 테스트 케이스
    T = int(input())

    # 테스트 케이스만큼 반복
    for _ in range(T):
        # N은 퇴사까지 남은 일수
        N = int(input())

        # 상담 일정 생성
        table = []
        for _ in range(N):
            t, p = map(int, input().split())
            table.append((t, p))
        print(table)
        # 최대 수익 초기화
        max_val = 0

        # 다이나믹 프로그래밍 함수 작성
        def dp(idx, pay):
            global max_val

            # idx가 퇴사 일수보다 커지면
            if idx >= N:
                # 구한 수익이 최대 수익보다 커질 경우 결과값에 추가.
                if pay > max_val:
                    max_val = pay
                return

            # 상담 일수와 수익 가져오기
            t, p = table[idx]

            # 반복문을 근무를 한다면, 근무를 안한다면으로 사용한다.
            # 아이디어 좋다.
            for i in range(2):
                # 근무를 한다면!
                if i == 1:
                    # 근무날짜가 남은 퇴사일보다 크면 종료
                    if idx + t > N:
                        return
                    # 아직 시간이 있으면 근무날짜에 상담날짜 추가
                    # 얻은 수익에 현재 수익 더해서 재귀 호출
                    dp(idx + t, pay + p)

                # 근무 안하면
                else:
                    # 근무날짜에 하루 추가, 수익은 그대로로 재귀 호출
                    dp(idx + 1, pay)
        dp(0, 0)
        print(max_val)

</aside>