Baekjoon 14728 벼락치기 JAVA

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

14728번: 벼락치기

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2014728

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 단원 수와 공부할 수 있는 시간이 주워지고

각 단원별 공부시간과 점수가 주어졌을 때

공부할 수 있는 시간 안에서 공부할 수 있는 최대 점수를 구하는 문제다.

딱 전형적인 냅색 문제였다.

​

해당 문제는 dp를 이용해서 해결했으며, 뒤에서부터 체크하는 방식으로 1차원 배열로 해결했다.

​

처음 입력 처리를 해준 뒤, 단원 수만큼 반복을 돌고 그 안에 공부할 수 있는 시간만큼 반복을 도는데

공부할 수 있는 시간은 끝에서부터 감소하도록 한다.

먼저 현재 시간에서 해당 단원의 공부시간을 뺸 것이 0보다 크거나 같다면

공부를 할 수 있기 때문에 비교를 해주는데

점화식은 dp[j] = Math.max(dp[j], S[i] + dp[j-K[i]]) 이 되는데

지금 dp[j]는 이전 단원에서의 해당 시간에 최댓값이 저장되어 있고,

S[i] + dp[j-K[i]]는 현재 단원의 점수 + 현재 시간에서 현재 단원의 공부 시간을 뺏을 때

이전 단원에서의 최댓값 합이 된다.

두 값은 비교해서 큰값을 dp 배열에 넣어주는 방식으로 문제를 해결했다.

​

주어지는 테케에서 예를 들면

첫 단원을 다 돌고 나면 dp 배열의 0~49는 0, 50~310은 40이 들어가게 되고

두 번째 단원을 돌고 나면 0~49는 0, 50~99까지는 40, 100~ 149는 70, 150~310은 110이 들어오게 된다.