[BOJ] 14501번: 퇴사 (Python)

📖  문제

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

💻  코드

 

BFS 풀이

import sys
from collections import deque


def solution():
    N = int(sys.stdin.readline().strip())
    plan = [(-1, -1)] + [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
    q = deque()
    q.append((1, 0))
    # 아무 상담도 못할 경우 대비
    res = 0
    # BFS
    while q:
        day, money = q.popleft()
        res = max(res, money)
        # 다음 날이 존재할 때
        if day + 1 <= N:
            # Case 1: 당일 상담 안 할 경우
            q.append((day + 1, money))
        # 퇴사일 전까지 상담을 마칠 수 있을 때
        if day <= N and day + plan[day][0] - 1 <= N:
            # Case 2: 당일 상담을 할 경우
            q.append((plan[day][0] + day, plan[day][1] + money))
    print(res)


solution()

 

DP 풀이

import sys


def solution():
    N = int(sys.stdin.readline().strip())
    plan = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
    dp = [0 for _ in range(N + 1)]

    for i in range(N):
        dp[i + 1] = max(dp[i], dp[i + 1])
        if i + plan[i][0] <= N:
            dp[i + plan[i][0]] = max(dp[i + plan[i][0]], dp[i] + plan[i][1])

    print(dp[N])


solution()

🙌  한마디

처음에 BFS로 풀었는데 DP로도 풀 수 있다길래 두 가지 방법으로 모두 풀어보았다. pycharm 환경에서는 결과가 잘 출력이 되는데 백준에 제출하면 TypeError가 발생해서 고민했었는데 알고보니 map()을 통해 입력받은 값을 list()로 감싸지 않아서 발생하는 문제였다. 이 점 앞으로 문제 풀 때 유의하자.