DATA101
[DP] 백준#14501: 퇴사/Python 본문
📝 문제
https://www.acmicpc.net/problem/14501
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
💡 접근법
다이나믹프로그래밍(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: 알고리즘 문제 풀이 및 정리
알고리즘 문제 풀이 및 정리. Contribute to park-gb/algorithm-problem-solving development by creating an account on GitHub.
github.com
해당 문제는 DFS 알로리즘으로도 해결 가능합니다. 이와 관련한 해설은 이곳을 참고해 주세요.
포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.
'알고리즘 > 문제풀이' 카테고리의 다른 글
[BFS/Combination] 백준#14502: 연구소/Python 풀이 (0) | 2022.04.27 |
---|---|
[DFS] 백준#14502: 연산자 끼워넣기/Python 풀이 (4) | 2022.04.26 |
[DFS] 백준#14501: 퇴사/Python (0) | 2022.04.26 |
[DFS] 백준#14500: 테트로미노/Python (0) | 2022.04.25 |
[알고리즘] 백준#13458: 시험 감독/Python (0) | 2022.04.24 |