Python3
문제
https://www.acmicpc.net/problem/14501
키워드
- 다이나믹 프로그래밍
- 브루트포스 알고리즘
문제 풀이
문제 요구사항
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
N = 7인 상담 일정표 예시)
1일 2일 3일 4일 5일 6일 7일
Ti 3 5 1 1 2 4 2
Pi 10 20 10 20 15 40 200상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
백준이가 얻을 수 있는 최대 수익을 구하는 프로그램
변수 및 함수 설명
- n: 퇴사하기 전 남은 상담 일수 (1 ≤ N ≤ 15)
- dp: 상담으로 얻을 수 있는 이익이 저장되는 리스트 (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
- arr: 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi이 저장되는 리스트
풀이
(입력 및 선언)
- 남은 상담 일수를 입력받는다
- n개의 t와 p를 입력받고 리스트에 저장한다
(최대 수익 구하기)
참고: na982 유튜브 퇴사
-
top-down 방식을 사용해 끝에서부터 처음으로 오는 반복문을 만들었다.
-
상담이 가능하면, 상담 스케줄을 진행하거나 안 하거나로 나뉠 수 있다.
- 만약 상담을 한다면, 현재 날짜 + 상담일수에 해당하는 dp에 얻을 수 있는 이익을 더한 값이 된다.DP[day + T[day]] + P[day]
- 상담을 하지 않는다면,
DP[day + 1]
이 된다. 둘 중 더 큰 값을 DP에 넣는다.
-
만약 현재 날짜와 상담 일수를 더했을 때, 퇴사해야 하는 일을 넘어간다면 상담을 하지 않는다.
(최종 출력)
- 가장 큰 값은 배열의 첫 번째에 저장되므로 첫 번째 원소를 출력한다.
최종 코드
n = int(input())
dp = [0 for _ in range(n+1)]
arr = [list(map(int, input().split())) for _ in range(n)]
for i in range(n-1, -1, -1):
if i + arr[i][0] <= n:
dp[i] = max(dp[i+arr[i][0]]+arr[i][1], dp[i+1])
else:
dp[i] = dp[i+1]
print(dp[0])피드백
혼자 시도해 보다가 na982님 유튜브 보고 아이디어를 얻어서 코드를 짰다.
역순으로 반복하는데 반복문 안에서 t, p를 입력받고 해당 값을 계산해서 답이 제대로 나오지 않았다. 이 부분은 결국 블로그를 보고 다시 수정했다.
dp의 정석 같은 문제라고 한다. 다음엔 bottom-up 방식도 코드를 짜서 수정해 보자.
