[백준/JAVA] 14501 - 퇴사

문제 정보

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

 

문제 

 

문제 해결 과정

완전 탐색 풀이

Ti와 Pi를 살펴보면, 상담기간이 길다고해서 상담금액이 큰 것이 아니었다. 즉, 상담기간과 상담금액은 랜덤하게 주어졌으므로, 그리디와 같은 방법으로는 접근할 수 없고 완전탐색이 필요한 문제이다.

 

각 날짜의 상담을 진행하거나 미진행할때의 모든 경우를 생각해보면, 가능한 경우의 수는 다음과 같다.

1일(상담/미상담) x 2일(상담/미상담) x ... x n일(상담/미상담) = 2^n가지

 

문제에서 n이 최대 15라고 주어졌으므로, 시간복잡도는 O(2^15)이므로 주어진 시간 내에 풀 수 있다.

---

하지만, 퇴사2와 같은 경우에는 n이 최대 1,500,000이므로 주어진 시간 내에 불가능하다.

그렇다면, 랜덤조건 내에서 시간을 줄일 수 있는 방법이라면 혹시 dp??

 

DP 풀이

dp의 정의를 다음과 같이 두가지 방식으로 정의하고, 각각에 대해 재귀와 반복문을 이용하여 구현해보았다.

	dp[i] : 첫째날부터 i일까지의 최대이익	dp[i] : i일부터 마지막날까지의 최대이익
재귀	X	①
반복문	②	③

 

①번 방법 : 재귀 + dp[i]는 i일부터 마지막날까지의 최대이익

class Main {	
	static int solveDp(int day, int n, int[] dp, int[][] schedule) {
		// 종료조건 (상담 가능 날짜 벗어난 경우)
		if(day > n) return 0;
		
		// 이미 계산된 적 있다면 => 재사용
		if(dp[day] != 0) return dp[day];
		
		// 해당 날짜에 상담 진행 o
		int take = 0;
		if(day + schedule[0][day] -1 <= n) {
			take = schedule[1][day] + solveDp(day + schedule[0][day], n, dp, schedule);
		}
		
		// 해당 날짜에 상담 진행 x
		int notTake = solveDp(day+1, n, dp, schedule);
		
		dp[day] = Math.max(take, notTake);
		
		return dp[day];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine()); // 남은 날짜
		int[][] schedule = new int[2][n+1]; // 상담 일정표 (0행: 시간, 1행: 비용)
		
		for(int i=1; i<=n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			schedule[0][i] = Integer.parseInt(st.nextToken()); // 상담시간
			schedule[1][i] = Integer.parseInt(st.nextToken()); // 상담비용
		}
		
		int[] dp = new int[n+1]; // dp[i]: i일부터 마지막날(n)까지의 최대이익
		
		solveDp(1, n, dp, schedule);
		
		System.out.println(dp[1]);
	}
}

 

②번 방법 : 반복문 + dp[i]는 첫째날부터 i일까지의 최대이익

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine()); // 남은 날짜
		int[][] schedule = new int[2][n+1]; // 상담 일정표 (0행: 시간, 1행: 비용)
		
		for(int i=1; i<=n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			schedule[0][i] = Integer.parseInt(st.nextToken()); // 상담시간
			schedule[1][i] = Integer.parseInt(st.nextToken()); // 상담비용
		}
		
		int[] dp = new int[n+1]; // dp[i]: 첫째날부터 i일까지의 최대이익
		for(int i=1; i<=n; i++) {
			// 해당 날짜에 상담 진행 o
			if(i + schedule[0][i] -1 <= n) {
				dp[i + schedule[0][i] -1] = Math.max(dp[i + schedule[0][i] -1], dp[i-1] + schedule[1][i]);
			}
			
			// 해당 날짜에 상담 진행 x
			if(i < n) {
				dp[i+1] = Math.max(dp[i+1], dp[i]);
			}
		}
		
		System.out.println(dp[n]);
	}
}

 

③번 방법 : 반복문 + dp[i]는 i일부터 마지막날까지의 최대이익

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine()); // 남은 날짜
		int[][] schedule = new int[2][n+1]; // 상담 일정표 (0행: 시간, 1행: 비용)
		
		for(int i=1; i<=n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			schedule[0][i] = Integer.parseInt(st.nextToken()); // 상담시간
			schedule[1][i] = Integer.parseInt(st.nextToken()); // 상담비용
		}
		
		int[] dp = new int[n+2]; // dp[i]: i일부터 마지막날(n)까지의 최대이익
		for(int i=n; i>=1; i--) {
			// 해당 날짜에 상담 진행 o
			int take = 0;
			if(i + schedule[0][i] -1 <= n) {
				take = dp[i + schedule[0][i]] + schedule[1][i];
			}
			
			// 해당 날짜에 상담 진행 x
			int notTake = dp[i+1];
			
			dp[i] = Math.max(take, notTake);
		}
		
		System.out.println(dp[1]);
	}
}