[DP] 백준#14501: 퇴사/Python

 

📝 문제

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

14501번: 퇴사

💡 접근법

다이나믹프로그래밍(DP)을 활용하여 해결하였습니다. DFS 알고리즘으로도 해결 가능합니다. 이와 관련한 해설은 이곳을 참고해 주세요. DP를 활용한 풀이는 다음과 같습니다. 저는 근무 가능일이 아닌 퇴사일로부터 근무가 가능한 첫 날까지 역순으로 근무 선택일에 따른 이익을 계산하였습니다. 즉, 퇴사일로부터 \(i\)번째까지 근무한 경우 이익은 \((i+1)\)까지 근무한 경우의 이익과 \((i+t)\)까지 근무한 경우의 이익 중 최댓값을 고르도록 로직을 작성하였습니다. 만일 해당 일에 근무하지 않으면 \(i\)번째 근무한 날까지 일한 이익은 \((i+1)\)까지 근무한 경우의 이익과 같기 때문에 값을 그대로 복사하면 됩니다. 즉, \(N\)일에 대한 연산이 끝났다면 이익의 합을 저장한 DP테이블의 [0] 인덱스 값이 최댓값으로 정답이 됩니다.

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline

def consult():
    for day in range(N-1, -1, -1):
        t = Work[day][0]  # 상담 소요일
        # 해당 일에 근무하는 경우
        if day + t <= N:
            p = Work[day][1]  # 상담 수입
            # 최대이익 선택
            dp[day] = max(dp[day + 1], dp[day + t] + p)

        # 해당 일에 근무하지 않는 경우
        else:
            dp[day] = dp[day + 1]

if __name__ == "__main__":
    N = int(input())
    Work = [list(map(int, input().split())) for _ in range(N)]
    dp = [0]*(N+1) # 최대수입 저장용 DP 테이블
    consult()
    print(dp[0])

2) 해설

(1) 데이터 입력 속도 개선

import sys; input = sys.stdin.readline

파이썬 내장함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.

(2) DP 구현

def consult():
    for day in range(N-1, -1, -1):
        t = Work[day][0]  # 상담 소요일
        # 해당 일에 근무하는 경우
        if day + t <= N:
            p = Work[day][1]  # 상담 수입
            # 최대이익 선택
            dp[day] = max(dp[day + 1], dp[day + t] + p)

        # 해당 일에 근무하지 않는 경우
        else:
            dp[day] = dp[day + 1]

\(day\)일의 이익은 \((day+1)\)에 근무했을 때의 이익과 \((day+t)\)일에 근무했을 때의 이익 중 최댓값을 고르면 됩니다. 만일 해당 일에 근무하지 않은 경우에는 근무일만 옮기면 되기 때문에 \(i\)번째 DP 테이블 값은 이전 값인 \(day+1)\)을 복사합니다.

(3) 메인함수

if __name__ == "__main__":
    N = int(input())
    Work = [list(map(int, input().split())) for _ in range(N)]
    dp = [0]*(N+1) # 최대수입 저장용 DP 테이블
    consult()
    print(dp[0])

✅ 채점 결과

정답 확인

위에 제출한 게 DP로 해결한 것이고, 아래에 제출한 코드는 DFS로 해결한 경우입니다. DFS 알고리즘으로 푼 해설은 이곳을 참고해 주세요.

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/dp/boj_14501.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

---

해당 문제는 DFS 알로리즘으로도 해결 가능합니다. 이와 관련한 해설은 이곳을 참고해 주세요.

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.