BOJ_S3_14501

📁 [S3_14501] 퇴사

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

public class Main{
	static StringTokenizer st;
	static int N;
	static int[][] arr;
	static int max = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		
		arr = new int[N][2];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			// [0] = 기간 , [1] = 금액
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		
		
		dfs(0,0);
		sb.append(max);
		System.out.println(max);
		
		
	}
	
	static void dfs(int day,int money) {
		
		// 기저조건 : 기간을 초과하는 경우
		if(day >= N) {
			max = Math.max(max, money);
			return;
		}
		
		for(int i=day; i<N; i++) {
			if(i+arr[i][0] <= N) {
				dfs(i+arr[i][0], money+arr[i][1]);
			}
			else{
				dfs(i+arr[i][0], money);
			}
		}
    }
}

🤔 나의 생각

dfs를 이용해서 풀어 주었다.
처음에 dfs에서의 i를 일수를 더해줘야 하는데 1을 더해주어서 문제가 있었다.
그리고 일수를 더했을때 N을 넘는 경우와 안넘는 경우를 나누어 재귀함수를 구현하였다.