[이코테 Ch16-33] 퇴사

👩🏻‍💻문제설명

[이코테 Ch16-33] 퇴사

✍️Idea Sketch

문제요약

남은 N일 동안 최대한 많은 상담을 하려고 한다. 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. 퇴사 전에 할 수 있는 상담의 최대 이익을 구하라.

시간복잡도

O(2^n)

각 날짜마다 상담을 하는 경우, 그렇지 않은 경우 총 2가지를 고려한다. 2 * 2 * 2 * … 총 n번 곱하므로 2^n이다.

알고리즘 : 브루트포스 알고리즘, 다이나믹 프로그래밍

브루트포스 알고리즘으로 구현했다. DFS로 상담을 하는 경우와 그렇지 않는 경우 둘 다 함수 호출했다. 그리고 정확히 퇴사날짜에 도달한 경우, 최대 이익을 계산한다.

✍️내 소스코드

• 종료조건 : 정확히 퇴사날짜 n에 도달한 경우, 최대 이익을 계산한다.
• n+1일째 이후부터는 회사에 없기 때문에, 최대 이익을 구할 수 없다. 따라서 depth가 n을 초과하는 경우 최대 이익을 계산하지 않는다.
• depth의 날짜에 상담을 하는 경우와 그렇지 않은 경우 둘 다 dfs 함수를 호출한다.

전체 코드

    import sys
    si = sys.stdin.readline


    def dfs(depth, price):
        global max_price
        if depth == n:
            max_price = max(max_price, price)
            return

        if depth > n:
            return

        t, p = seq[depth]
        dfs(depth + t, price + p)
        dfs(depth + 1, price)


    if __name__ == "__main__":
        n = int(si())
        seq = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

        max_price = 0
        dfs(0, 0)
        print(max_price)