[백준 15486번 퇴사 2]
오늘의 문제는 " 퇴사 2"이다.
#고민의 흐름
처음엔 무조건 완전탐색!
오늘의 DP문제 ~
문제를 보아하니 150만까지의 날짜수를 했을 때, 안 했을 때를 나눠서 다계산해주면
필연적으로 시간초과가 날수밖에 없다고 생각했다.
결국 어떠한 규칙을 찾아 나날이 가장 최선의 값을 가지며,
그게 뒷날짜에도 최선을 보장할 수 있도록 기록을 해나가야 하는 거 같은데 ,,,
일단, 시간초과지만 고민하다가 처음 생각해 냈던 방법은 다음과 같다.
1. 해당 날짜로부터 소요 날짜만큼 계산했을 때 상담 가능 / 불가능 체크한다.
2-1 불가능시 무시 후 다음 날짜 1로.
2-2 가능시 dp [해당 날짜] = dp[해당 날짜] + 해당 날의 금액
3. dp [해당날짜 + 해당날의 상담시 소요날짜]와 2-2에서 갱신된 dp[해당 날짜]를 대소비교 후 큰 값을
dp [해당날짜 + 해당날의 상담 시 소요날짜] = 둘 중 더 큰 수
이와 같은 규칙으로 dp 배열을 채워나갔다.
그 결과 문제 예제 4번의 8일 차가 되는 날,
6일 차에서 7일 차 상담을 하지 않고 8일 차를 받아들이는 경우가 고려되지 않음을 알 수 있었다.
그래서 해당 경우를 해결하기 위해서, 다음과 같은 코드를 추가했다.
1. 가능 / 불가능 체크
2-1 불가능시 무시 후 다음날짜 1로
2-2 가능시
2-2-1 dp [해당날짜]가 아직 0일 때,
해당날짜 ~ 1일 차까지 중에 가장 큰 dp [i]를 dp [해당날짜]에 두고 이어나간다.
2-2-2 dp [해당날짜] 이미있으면 그대로 진행.
결과는? 시간초과였다 ㅎ
아무래도 dp[해당 날짜]가 0인 경우 그전의 모든 날짜의 dp [i]를 확인해 주는 부분이 너무 오래 걸리는 것 같았다.
상담 소요날짜가 모두 1이라 하더라도 바로 다음날짜까지
즉, 당일은 dp [i]가 0이 아니기 때문에 문제가 안될 거라 생각했는데 아닌가 보다..
dp 배열을 다시 채워야겠다,, 새로이 해야겠다.. 를 생각하다가 일단 포기!
다음날 문제를 다시 마주하게 되었다.
한동안 생각을 안 하다가 새로이 생각하게 되어서 그런지 아이디어가 떠올랐다!
그림과 함께 확인하자!
예제 4번을 예시로 사용했다!
idx = 0 부분은 생략했다! N+1은 설명상 필요하니 일단 두었다. 초기상태는 아래와 같다!
규칙은 다음과 같다.
1. 상담 가능한 날 / 불가능한 날 판단.
2-1 불가능한 날이라면 temp = dp [i]만 해준다.
2-2 가능한 날이라면 dp [ i + T [i] ] ( dp [그날 상담 시 다음 상담 가능 날짜] )에
dp [i] + T [i]와 dp[ i + T[i] ]을 대소비교 후 큰애를 넣어준다.
그리고 temp와 dp [i]를 대소비교 후 큰 애를 temp에 넣어준다.
이렇게 가다 보면 예시의 8일째 되는 날. 2-2 동작을 위해서 N+1이 필요하다.
이젠 순서대로 그림과 함께 설명을 들어보자.
1. 상담 가능
2-2. 상담 시 다음 가능날짜 = 6
dp [6] = temp ( temp와 dp [1] 중 크거나 같은 애) + P [1] = 50
temp = 0
2일 차 ~ 5일 차까지는 상담 가능하지만
이후 상담 가능 날짜인 dp [6]의 값과 dp [i] + P [i] 값을 비교 시
기존의 값이 더 크기 때문에 차이가 없다.
6일 차
1. 상담가능
2-2 상담 시 다음 날짜 = 7
dp [7] = temp ( temp와 dp [6] 중 크거나 같은 애) + P [6] = 50
temp = Math.max(temp, dp [6]) = 50
7일 차
1. 상담가능
2-2 상담 시 다음 날짜 = 9
dp [9] = dp [7]( temp와 dp [7] 중 크거나 같은 애) + P [7] = 80
temp = Math.max(temp, dp [7]) = 60
8일 차
1. 상담가능
2-2 상담 시 다음 날짜 = 11 ( N+1 )
dp [11] = temp ( temp와 dp [8] 중 크거나 같은 애) + P [8] = 90
temp = Math.max(temp, dp [8]) = 60
9일 차, 10일 차는 상담 불가이므로 패스.
이 모든 과정이 끝나고 dp [i]를 처음(1)부터 N+1까지 돌면서 최댓값을 ans에 저장하고 출력해 줬다.
이번엔 코드와 함께 보자!
코드는 다음과 같다.
( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )
( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )
import java.util.*;
import java.io.*;
public class Main {
public static void main(String [] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
int [][] info = new int [2][N+1]; // 그림에서의 T와 P를 info로 한번에 작성했다.
// [0]이 T, [1]이 P이다.
for(int i = 1; i<N+1; i++){
st = new StringTokenizer(br.readLine());
info[0][i] = Integer.parseInt(st.nextToken());
info[1][i] = Integer.parseInt(st.nextToken());
} // 입력받아주고
int ans = 0; // 답이 되줄 ans !
int [] dp = new int[N+2]; // 우리는 N+1까지 필요하니까 !
int temp = 0; // temp도 선언해주고,
for(int i = 1; i<N+1; i++){ // 1부터 N까지 반복하면서 ~
if(i + info[0][i] - 1 <= N){ // 상담 가능 날이라면,
if(dp[i] != 0){ // dp[i]가 0이 아니면 temp 갱신 !
temp = Math.max(temp, dp[i]);
}
// 다음 상담 가능 날짜에 해당하는 dp값
int t = temp + info[1][i];
// 이미 있는수랑 대소비교후 크면 넣어준다.
if(t > dp[i + info[0][i]]){
dp[i + info[0][i]] = t;
}
}else{ // 불가한 날이라면,
//불가한 날이라도 dp[i]가 temp보다 크면 갱신해준다.
//해당 날짜 일안하더라도 더 나은 temp값이 될 수 있으니까 !
if(dp[i] != 0){
temp = Math.max(temp, dp[i]);
}
}
}
//전체 돌면서 최대ans구해주고 !
for(int i = 1; i<N+2; i++){
ans = Math.max(ans, dp[i]);
}
// 출력하면 끝!
System.out.print(ans);
}
}
기세 좋게 이전에 틀렸던 문제를 풀어보려 들어갔다가
2시간 동안 고민만 하고 시간초과 나고 혼이 났다 ,,
다음날 낮, 다시 재도전하고 고민한 결과 문제를 풀어낼 수 있었다.
dp문제를 풀 때마다 느끼지만 TC에서 제시되지 않은 히든 TC를 실전에서 혼자 찾아낼 수 있을지 항상 의문이다..
이렇게 하다 보면 언젠간 dp문제 질문게시판을 보지도, 따로 찾아보지도 않고 한 번에 맞는 날이 오겠지?
파이팅이 다아~
궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~
https://www.acmicpc.net/problem/15486