👩‍💻 문제

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

🙋‍♀️ 답변

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] T = new int[N+1]; // 걸리는 시간
		int[] P = new int[N+1]; // 급여
		int[] D = new int[N+2]; // N+1일까지 저장할 공간
		
		for (int i =1; i<=N; i++) {
			T[i] = sc.nextInt();
			P[i] = sc.nextInt();
		}
		
		// DP 계산 (거꾸로 탐색)
		for (int i=N; i>0; i--) {
			if (i + T[i] <= N+1) {
				D[i] = Math.max(D[i+1], P[i]+D[i+T[i]]);
			} else {
				D[i] = D[i+1];
			}
		}
		
		System.out.println(D[1]);
		sc.close();
		
	}

}

💡

어제 아니고 그제 현대캐피탈 코테를 봤는데 비슷한 문제가 나왔다. 비슷한 문제를 찾아서 풀어보려고 했는데 전혀 모르겠어서 풀이를 찾아봤다. 풀이를 읽어봐도 이해가 안 가서 유튜브에서 풀이 영상을 봤다. 드디어 이해가 됐다 !! 한 90% 정도,,,ㅋ.ㅋ 하지만 다른 DP 문제가 나오면 못 풀 것 같다. 헹헹

내가 본 유튜브 풀이 영상 첨부. (유튜브다)