[백준] 14501. 퇴사(실버4)

백준(실버4) - 14501. 퇴사(실버4)

---

---

풀이

재귀로 풀었다!
약간 부분집합 생각하면서 풀게 되었다.
각 요일마다 2가지의 선택지가 있다. 해당 날에 상담을 할 경우와 하지 않을 경우!
상담을 하지 않은 날에는 날짜만 하루 올려주고 다시 solve를 호출한다.

		//선택하지 않았을 경우
		solve(day+1, sum);	

선택했을 경우에는 상담이 걸리는 기간과 day를 더해주고, 상담을 하고 받는 돈을 sum에 더해준 후 solve를 호출해준다.
solve를 호출하기 전에 퇴사 전인지도 체크해주어야 한다.

		//선택했을 경우-day체크도 해야한다.
		if(arr[day][0] + day<=n)
			solve(day+arr[day][0],sum+arr[day][1]);

전체 코드는 아래와 같다.

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

public class Main {
	static public int max,n;
	static public int[][] arr;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		arr = new int[n][2];
		
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		
		max = 0;
		solve(0,0);
		System.out.println(max);
	}
	
	static public void solve(int day, int sum) {
		//기저조건
		if(n == day) {
			max = Math.max(max, sum);
			return;
		}
		
		//선택했을 경우-day체크도 해야한다.
		if(arr[day][0] + day<=n)
			solve(day+arr[day][0],sum+arr[day][1]);
		
		//선택하지 않았을 경우
		solve(day+1, sum);	
	}
}