1. 학습한 내용
백준 동적프로그래밍 14501번 문제
2. 알게 된 내용
문제 풀이 아이디어 관련해서...
각 날짜를 하나씩 탐색하면서, 각 날짜까지의 최대 보수 값을 dp에 저장하면 된다.
그런데, 문제의 예시에서, 첫째날에 일을 하게 되면 1,2,3일차까지는 벌 수 있는 돈이 없다고 생각하고 3일째까지는 돈이 0원이라고 dp에 담아야 한다. 나는 일단 처음에 받는다고 생각하고 진행해서 잘 안 풀렸는데, 이 일한 값은 다 일하고 나서 받는다고 생각하면 편하다.
그 이후에는,
i = i일에 시작하는 상담
day = 각각 상담 일수를 담은 배열
pay = 각각 상담에 대한 보수를 담은 배열
이라고 했을 때,
i일에 시작하는 상담을 진행한 후 그 다음 가능한 상담에 대해
dp[i + day[i]] = Math.max(dp[i + day[i]], pay[i] + dp[i])
로 구할 수 있다.
- dp[i + day[i]] : i일에 시작한 상담을 진행한 후의 다음 시작 상담을 시작할 때 최대 보수
- pay[i] + dp[i] : i일째의 최대 보수 + i일에 시작하는 상담에 대한 보수
출처 및 참고 :
기록하자
0개의 댓글
