[백준 python] 14501번 퇴사

문제링크

문제 설명

• N+1일째 퇴사를 하기로 하고 N일까지 상담을 할 수 있을 때 최대로 받을 수 있는 수익을 계산하는 문제
• 매일 다른 상담을 선택할 수 있지만 상담에 소요되는 시간과 상담 비용은 모두 다르다

고민한 부분

• 단순히 loop를 순회하며 풀이할 수 있을 것이라고 생각했지만 해결하지 못해 다른 분들의 풀이를 공부했다.
• dynamic programming이라는 방법으로 풀 수 있었는데 dynamic programming은 프로그램 중간에 계산된 결과를 다른 공간에 저장해두고 이후에 참조해 사용하는 방식이다

	import sys
	def solve$N, table$:
	dp = [0]*$N+1$
	for i in range$N-1, -1, -1$:
	if i + table[i][0] > N:
	dp[i] = dp[i+1]
	else:
	dp[i] = max$dp[i+1], table[i][1] + dp[i + table[i][0]]$
	return dp[0]
	if __name__ == '__main__':
	turn_in = 1
	if turn_in == 0:
	sys.stdio = open$'test_case.txt'$
	N = int$sys.stdio.readline($)
	table = [list$map(int, sys.stdio.readline($.split)) for i in range$N$]
	else:
	N = int$sys.stdin.readline($)
	table = [list$map(int, sys.stdin.readline($.split)) for i in range$N$]
	# 오늘 공부한 dynamic programming 방법으로
	sol = solve$N, table$
	print$sol$

view raw boj_14501.py hosted with ❤ by GitHub

Lesson learned

• dynamic programming이라는 개념을 알고는 있었지만 관련된 문제를 해결해 본 적은 없었다.
• 이번 문제는 다른 분들의 풀이를 보고 이해했지만 비슷한 문제가 나왔을 때 해결할 수 없을 것 같아 다른 dynamic programming 문제들을 풀이해봤다.
• 공부한 내용은 따로 포스팅 올릴 계획.