[14501] 퇴사

Benjamin·2023년 4월 28일

BAEKJOON

목록 보기

57/71

완전탐색은 너무 오래걸리며, dp의 사용조건인 '겹치는 부분 문제'와 '최적 부분 구조'가 다 성립하므로 DP를 사용해 풀었다.

💁‍♀️ DP 사용!

Troubleshooting

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

public class Main {
static int[][] info;
static int[] payment;
static int[] finishDay;
static boolean[] isFinish;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		info = new int[N+1][2];
		payment = new int[N+1];
		finishDay = new int[N+1];
		isFinish = new boolean[N+1];
		
		for(int i=1; i<=N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int T = Integer.parseInt(st.nextToken());
			int P = Integer.parseInt(st.nextToken());
			info[i][0] = T;
			info[i][1] = P;
			payment[i] = P;
			finishDay[i] = i+T;
			if(finishDay[i] > N+1) finishDay[i] = Integer.MAX_VALUE;
		}
		dp(N);
		for(int i=N; i>0; i--) {
			if(payment[i] != Integer.MAX_VALUE) {
				System.out.print(payment[i]);
				break;
			}
		}
	}
	public static void dp(int N) {
		for(int i=2; i<=N ; i++) {
			if(finishDay[i] == Integer.MAX_VALUE) {
				payment[i] = Integer.MAX_VALUE;
				continue;
			}
			for(int j=1; j<i; j++) {
				if(finishDay[j] <= i && !isFinish[j]) {
					isFinish[j] = true;
				}
				if(isFinish[j]) {
					payment[i] = Math.max(payment[i], payment[j] + info[i][1]);
				}
			}
		}
	}
}

문제

테케는 다 맞았는데, 틀렸습니다를 받았다.

질문게시판에서 나와 답이 다르게 나온 예외 테케를 발견했다!

5
5 10
1 1
1 1
1 1
1 1

# Output
4
    
# Answer
10

원인

내 코드대로라면 payment배열에 누적된 값은 {10,1,2,3,4}이다.
하지만 1일에 시작한 일은 딱 기한마지막날(5일)에 마무리되므로 payment[5]의 값이 아니라 payment[1]의 값이 출력되어야한다!

주어진 마지막날의 다음날까지가서 끝난 일이 있는지 체크하고 최대금액을 뽑았어야하는데, 마지막일자까지만 체크했다.

해결

payment의 크기를 하나 늘려서 마지막 날 다음날까지 기준으로해서 마지막날에 끝나는 일을 체크할 수 있게했다.

그리고 출력은 결국 payment[N+1]을 해주면 된다.

제출 코드

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

public class Main {
static int[][] info;
static int[] payment;
static int[] finishDay;
static boolean[] isFinish;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		info = new int[N+1][2];
		payment = new int[N+2]; //예외 : 마지막날의 다음날까지 계산필요 (마지막날에끝나는 일 체크위해)
		finishDay = new int[N+1];
		isFinish = new boolean[N+1];
		
		for(int i=1; i<=N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int T = Integer.parseInt(st.nextToken());
			int P = Integer.parseInt(st.nextToken());
			info[i][0] = T;
			info[i][1] = P;
			payment[i] = P;
			finishDay[i] = i+T;
			if(finishDay[i] > N+1) finishDay[i] = Integer.MAX_VALUE;
		}
		dp(N);
		System.out.println(payment[N+1]);
	}
	public static void dp(int N) {
		for(int i=2; i<=N ; i++) {
			if(finishDay[i] == Integer.MAX_VALUE) {
				payment[i] = Integer.MAX_VALUE;
				continue;
			}
			for(int j=1; j<i; j++) {
				if(finishDay[j] <= i && !isFinish[j]) {
					isFinish[j] = true;
				}
				if(isFinish[j]) {
					payment[i] = Math.max(payment[i], payment[j] + info[i][1]);
				}
			}
		}
		
		//예외 코드
		for(int i=1; i<=N; i++) {
			if(finishDay[i] <= N+1 && !isFinish[i]) {
				isFinish[i] = true;
			}
			if(isFinish[i]) {
				payment[N+1] = Math.max(payment[N+1], payment[i]);
			}
		}
	}
}

모범 답안

나는 배열의 첫 원소(1일)부터 누적하는 방식을 사용했는데, 책의 풀이를 보니 가장 마지막일부터 체크해서 누적하는 방식도 있길래 공부한다.

import java.io.IOException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] D = new int[N+2]; //최대 수입 저장 배열
		int[] T = new int[N+1];
		int[] P = new int[N+1];
		for(int i=1; i<=N; i++) {
			T[i] = sc.nextInt();
			P[i] = sc.nextInt();
		}
		for(int i= N; i>0 ;i--) {
			if(i + T[i] > N+1) D[i] = D[i+1];
			else D[i] = Math.max(D[i+1], P[i]+D[i+T[i]]); // 해당일의 일을 안하는게 더 많은지, 해당일 전의 해당 일수의 일을 하는게 더 많은지
		}
		System.out.println(D[1]);
	}
}