[백준] 15486 퇴사 2 - Dynamic Programming / Java

• 문제 링크

15486번: 퇴사 2

 

• 풀이 과정

아래 링크는 n의 범위가 다르지만 내용은 같은 문제로 완전 탐색으로 풀이했고 이번엔 DP로 풀이했다.

[백준] 14501 퇴사 - Brute Force / Java

 

우선 총 상담일의 수 n, 지정된 상담 소요일과 수익을 t배열, p배열에 각각 저장하고 비교값을 메모이제이션할 dp 배열을 추가로 생성한다.

 

 i + t[i] 은 현재 날짜 + 상담 소요일을 의미하며 이 값이 n + 1 이하인 조건에 의해 현재 날짜를 포함한 상담 소요일이 총 주어진 날짜를 초과하지 않아야 비교가 진행된다.

 

현재 날짜까지의 수익(dp[i]) 과 이번 상담에 벌어들일 수익(p[i]) 을 합한 값, dp[i] + p[i] 와

상담 소요일이 지난 후 날짜의 예상 수익, 즉 dp[i + t[i]] 와 비교하여 큰 값을 dp[i + t[i]] 인덱스 위치에 저장한다.

즉 비교한 값을 상담 소요일이 지난 시점의 총 수익으로써 미리 메모이제이션 해둔다.

맨 처음 반복문이 시작될 때 dp[i + t[i]] 는 0 이므로 dp[i] + p[i] 이 Math.max 에 의해 저장된다.

 

이런 식으로 반복문이 이어짐과 동시에 dp[i + 1] = Math.max(dp[i + 1], dp[i]) 로 현재 인덱스와 이전 인덱스 중

큰 값을 뒤로 이동시켜 결과적으로 dp 배열의 내의 가장 큰 값이 dp[n + 1] 로 이동되며 이 값이 최대 수익이 된다.

 

• 풀이 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int[] t = new int[n + 1];
		int[] p = new int[n + 1];

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

		int[] dp = new int[n + 2];
		for (int i = 1; i <= n; i++) {
			if (i + t[i] <= n + 1) {
				dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
			}
			dp[i + 1] = Math.max(dp[i + 1], dp[i]);
		}

		bw.write(dp[n + 1] + "\n");
		bw.flush();
	}

}