백준14501 퇴사 (Java 자바)

생각보다 쉬운 문젠데 brute force로 푸는 방법과 dp로 푸는 방법 두 가지가 있다고 한다.

나는 brute force로 풀었는데 dp로 다시 풀어볼 예정이다. 

import java.util.Scanner;
import java.util.Stack;

public class bj14501 {
	static int income[][];
	static int N, Max, money;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		
		N = sc.nextInt();
		income = new int [N][2];
		
		for (int i = 0; i < N; i++) {
			//0번째 열에는 걸리는 시간
			income[i][0] = sc.nextInt();
			//1번째 열에는 얻을 수 있는 돈
			income[i][1] = sc.nextInt();
		}
		quitC(0, 0);
		System.out.println(Max);
		
	}
	
	static void quitC(int idx, int sum) {
		if(idx >= N) {
			if(sum > Max) {
				Max = sum;
			}
			return;
		}
		if(idx + income[idx][0] <= N) {
			quitC(idx + income[idx][0], sum + income[idx][1]);
		}
		quitC(idx + 1, sum);
	}
}