알고리즘 스터디 5주차 2

14501

• 알고리즘 : DP
• 난이도 : 실버3

문제

14501

접근

• 점화식을 찾는 것이 어려웠다.
• 손으로 먼저 풀어보고 점화식을 구했다.
  • index + days[index] <= N

가정

• DP 문제는 점화식을 구하는 것이 핵심

풀어보기

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws IOException {
		// index + days[index] <= N
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(reader.readLine());
		int[] days = new int[N];
		int[] money = new int[N];
		int totalMoney = 0;

		for(int i = 0; i < N; i++) {
			String[] lines = reader.readLine().split(" ");
			days[i] = Integer.parseInt(lines[0]);
			money[i] = Integer.parseInt(lines[1]);
			}

		int[] dp = new int[N+1];
		for(int i = 0; i < N; i++) {
			if(i+days[i]<= N){
				//날짜가 넘지않아야 함.
				//다음 계산될 날짜의 값은 기존값과 새로 계산된 값을 비교하여 큰 수를 저장
				dp[i+days[i]] = Math.max(dp[i+days[i]], dp[i] + money[i]);
			}
			// days가 넘지 않은 범위에서 다음 index와 계산되어야함 3일차의 값은 1이 아닌 100이 되어야함
			dp[i+1] = Math.max(dp[i+1], dp[i]);
		}
		System.out.println(dp[N]);
	}
}

시행착오

• 사실 점화식은 구했지만 이 점화식을 어떻게 적용시킬 지 고민이 되었다.
• 배열을 따로 구해 해당 배열에 최대값을 넣는 코드가 핵심 코드
• 날짜를 순차적으로 계산 한다면 값이 나오지 않는다.
• 다른 반례가 필요했다.

참고자료