알고리즘/백준

[백준 15486번 퇴사 2]

익명의 문과 개발자 2024. 9. 11. 16:56
728x90
728x90

오늘의 문제는 " 퇴사 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

 

 

728x90