문제

💡문제 분석 요약

• 상담을 진행하면 각 상담별 정해져 있는 페이를 받는다.
• 상담의 기간 동안은 다른 상담을 진행할 수 없다.
• 최대 수익은?

💡알고리즘 설계

• DP 를 활용하여 각 날짜별 받을 수 있는 최대 페이의 값을 저장해가며 마지막 날의 값을 출력한다.

💡코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int[][] data;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		data = new int [N+1][2];
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			data[i][0] = Integer.parseInt(st.nextToken());
			data[i][1] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(dp());
		
	}
	
	private static int dp() {
		int[] dp = new int[N+2];
		
		for (int i = 1; i <= N; i++) {
			// 오늘 작업의 결과 반영 (상담 끝난 다음날 저장됨)
			int next = i + data[i][0];
			if (next <= N +1) {
				dp[next] = Math.max(dp[next], dp[i] + data[i][1]);
			}
			
			dp[i+1] = Math.max(dp[i+1], dp[i]);
		}
		return dp[N+1];
	}
}

💡시간복잡도

두번의 반복문으로 2N이기에 최종적으로 N의 시간복잡도를 갖는다.

💡 틀린 이유

DP 로 접근하여 각 날짜마다 정보를 저장해가며 풀어야 겠다는 로직은 떠올랐으나
최대 값을 어떻게 구해 나가야 할지 접근하기 어려웠다.

💡 느낀점 or 기억할정보

• DP 문제를 좀 더 풀어 보자!
• 각 날짜별 값을 저장하는 방식에 익숙해지자