/ BOJ

BOJ_14501_퇴사_JAVA

문제 : 퇴사

링크 : BOJ_14501_퇴사

접근 방식

1~N일 까지의 각각의 상담 일정이 주어지고, N일까지 가장 큰 수익을 얻을 수 있는 경우의 수를 찾아야 한다.

1일부터 시작하여 값은 계속해서 증가할 수밖에 없다. 따라서 특정 날짜의 일을 선택하는지 선택하지 않는지에 따라 누적비용을 다르게 하여 경우의 수를 따져볼 수 있다. 나는 DFS를 이용한 완전탐색을 사용하면 풀 수 있을 것이라고 생각했다.

풀이 방법

  1. 남은 날짜의 값을 읽어와 N 변수에 저장하고, 각 날짜별 상담의 일정과 비용을 2차원 배열로 저장한다.

  2. dfs를 돌린다. 인자값으로는 날짜를 체크할 int 값과, 누적된 비용을 저장할 int 값을 받는다.

  3. dfs 내부에서의 기저조건은 날짜가 N에 도달했을 때 멈추도록 한다. 추가적인 가지치기로, 날짜가 N을 넘어섰을 때도 return 시켜준다.

  4. 이제 재귀호출을 하는데, 현재 날짜의 상담을 받아들이지 않는 경우, 기존 날짜에는 1을 더해주고 일을 받지 않았으므로 누적된 비용은 그대로 넘겨서 재귀호출 해준다.

  5. 반대로 현재 날짜의 상담 일정을 받아들이는 경우, 상담 일정만큼은 다른 일을 할 수 없기 때문에 현재 날짜에서 상담 기간만큼 날짜를 더해주고, 비용 또한 누적시켜 재귀호출시켜준다.

  6. 날짜가 N에 도달한 기저조건에서, 비용의 최댓값을 저장하도록 한다.

  7. dfs 탐색이 모두 끝난 후 비용의 최댓값을 출력한다.

소스 코드

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

public class BOJ_14501_퇴사 {
	static int N;
	static int arr[][];
	static int answer;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());

		StringTokenizer st;
		arr = new int[N][2];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j=0;j<2;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dfs(0,0);

		System.out.println(answer);
	}


	public static void dfs(int cnt, int sum) {

		if(cnt == N) {
			answer = Math.max(answer,sum);
			return;
		}

		// 가지치기 1
		if(cnt >= N) {
			return;
		}

		// 현재 위치를 선택하지 않는 경우
		dfs(cnt+1, sum);

		// 현재 위치를 선택하는 경우
		sum = sum + arr[cnt][1];
		cnt = cnt + arr[cnt][0];

		dfs(cnt, sum);

	}

}