[백준] 14501. 퇴사 - 실버5

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

14501번: 퇴사

 

문제 요약

상담원은 오늘부터 N+1째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

매일매일 상담을 잡아 놓았지만 상담마다 완료하는 데 걸리는 기간과 받을 수 있는 금액이 다르다.

1일에 하는 상담이 3일 걸린다면, 4일부터 또 다른 상담이 가능하다.

이런 경우에 N일 동안 상담원이 얻을 수 있는 최대 수익은?

 

문제 해결 아이디어

먼저 입력받은 상담을 선택하느냐, 하지 않느냐 두 가지의 선택지가 있는 것이라고 생각하고 부분집합으로 풀겠다는 아이디어를 떠올렸다.

하지만 단순 부분집합은 아니고, 상담마다 겹치면 안 되기 때문에 부분집합을 구하는 재귀함수 안에 조건을 여러 개 부여했다. isSelected[] 배열은 해당 날짜를 선택하면 true, 선택하지 않으면 false가 들어가는 배열이다.

재귀함수의 파라미터는 int i로 상담을 할지 말지 고려할 날짜이다. 

먼저 이미 i가 끝 날짜에 다다른 경우, 즉 상담을 고려할 날짜가 N을 넘어가 버리는 경우에는 어쨌든 상담을 할 수 없으므로 바로 return; 해 줬다.

다음은 현재 날짜, i번째 날에 상담을 하기로 한다면 i+t[i], 즉 현재 날짜의 상담이 끝나는 시간을 체크해 줘야 하는데 그게 N을 넘어가 버리면 해당 날짜의 상담은 불가능하다. 따라서 isSelected[i]를 false로 체크해 주고 다음 상담 날짜를 본다.

마지막으로 만약 상담이 가능하다면 현재 날짜를 선택할지 말지 둘 다 생각해 줘야 한다. 선택하지 않는 경우가 더 이득일 수도 있기 때문이다. 그래서 두 가지 경우를 모두 탐색한다.

재귀함수가 기저조건에 다다랐을 때 isSelected가 true인 날짜의 이익을 다 더해서 최대값을 찾아 주었다.

 

완성된 코드

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

public class Main_BOJ_14501_퇴사 {
	static int N;
	static int[] t;
	static int[] p;
	static boolean[] isSelected;
	static int sum;
	static int max;

	public static void main(String[] args) throws Exception {
		// N일 동안 최대한 많은 수익을 낼 수 있는 방법을 찾는다
		// 입력이 15개까지므로 모든 경우의 수를 본다
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		t = new int[N];
		p = new int[N];
		isSelected = new boolean[N];
		sum = 0;
		max = Integer.MIN_VALUE;

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			t[i] = Integer.parseInt(st.nextToken());
			p[i] = Integer.parseInt(st.nextToken());
		}

		pick(0);
		System.out.println(max);
	}

	// 그 상담을 선택하느냐 하지 않느냐 -> 부분집합
	// 예외 조건은 앞에 선택한 날짜와 겹쳐버리면 선택하고 싶어도 못함. 최대한 적게 선택하는 방법
	public static void pick(int i) {
		if (i >= N) { // 끝 날짜에 다다른 경우 (마지막 날은 하고 싶어도 못함)
			sum();
			return;
		}

		if (i + t[i] > N) { // 상담할 수 있는 날짜를 넘어선 경우 현재 날짜 상담은 무조건 불가능함
			isSelected[i] = false;
			pick(i+1);
		} else { // 아직 범위 안에 있는 경우는 현재 날짜의 상담을 할지 말지 둘 다 생각해 줘야 함
			isSelected[i] = true;
			pick(i + t[i]);
			isSelected[i] = false;
			pick(i+1);
		}
	
	}

	public static void sum() {
		for (int i = 0; i < N; i++) {
			if (isSelected[i])
				sum += p[i];
		}

		max = Math.max(max, sum);
		sum = 0;
		return;
	}
}// end of class