[백준] 14504 - 퇴사 (JAVA)

소요시간

30분 정도 걸렸다. 점화식을 유도해내는게 쉽지 않았다. 아직 DP 유형이 많이 어색하다. 그래프 이론 문제는 골드 문제여도 어렵지 않게 느껴지는데 그리디 알고리즘이나 DP 유형은 아직 많이 부족하다.

문제유형 & 티어

DP 유형이다. 처음부터 문제의 알고리즘의 유형을 알고 풀었다.
그리고 티어는 실버 3의 수준이다.

풀이과정

가장 고민한 부분 : 점화식은 무엇일까?

1. 우선 각각의 값을 저장할 dp 배열, cost 배열 ,pay 배열을 선언해준다. dp 배열의 값을 10000으로 지정해 준 이유는 곧 설명하겠다.
2. for문으로 dp 배열의 값을 지정해주는데 만약 이전의 dp값이 더 크다면 이전의 dp 값을 따른다. 즉, dp[i] = Math.max(dp[i], dp[i-1]) 이다.
3. 이제 이 부분이 중요한데, dp[i+price-1] 은 우선 1일차를 예시로 든다면 cost[1] 은 3으로, 즉 그것이 price가 된다. 계산을 해주면 dp [ 1 + 3 -1] 은 dp[3] 이 되고, 이는 1일차의 3일을 소요하는 것은 dp[3] 의 값이 된다는 것이다. 결국 dp[3] 은 dp[3] 과 dp[2] + pay[1] 이 된다.
4. 그렇게 총 for문으로 계속 갱신을 해주는데, 여기서 예외처리 해야할 부분은 테스트케이스 1의 6일차이다. 이 경우에는 dp[i+price-1] 이 dp[7] 을 넘어서 dp[9] 까지 가게 되는데 이 때 dp 배열의 크기를 7까지로 지정해주면 에러가 난다. 그렇기에 여유분으로 dp 배열의 크기를 크게 지정해주었다. 물론, i+price-1 이 dp의 길이를 넘어가면 continue 해주는 방법도 있지만, 여기서는 가장 직관적인 코드를 짰다. (메모리 관점에서는 비효율적)
5. 가장 마지막 dp[n] 값은 for문으로 dp[i]= Math.max(dp[i], dp[i-1]) 이므로 가장 큰 값임을 보장받을 수 있다. 최종적으로 dp[n] 을 출력한다.

시간복잡도는 for문이 1번 도므로 o(n) 일 것이다.

소스코드

import java.io.*;
import java.util.*;

 
 
public class Main{
 
   
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb=new StringBuilder();
        
        int n=Integer.parseInt(br.readLine());
        int dp[]=new int[10000];
        int cost[]=new int[n+1];
        int pay[]=new int[n+1];
        for(int i=1;i<=n;i++) {
        	st=new StringTokenizer(br.readLine());
        	int a=Integer.parseInt(st.nextToken());
        	int b=Integer.parseInt(st.nextToken());
        	cost[i]=a;
        	pay[i]=b;
        }
        
        for(int i=1;i<pay.length;i++) {
        	int price=cost[i];
        	dp[i]=Math.max(dp[i], dp[i-1]);
        	dp[i+price-1] =Math.max(dp[i+price-1], dp[i-1]+pay[i]);
        }
        
        
      System.out.println(dp[n]);
 
 
    }
 
}

결과

회고

1줄 요약: dp 유형이 너무 부족하다.

이번에 모 코딩테스트를 본적이 있었는데 가장 어려웠었던 문제로 플로이드-워셜 알고리즘과 DP를 섞은 혼종이 나왔었다. 그래프 이론은 개인적으로 가장 자신있는 분야였기 때문에 문제를 보자마자 플로이드-워셜 알고리즘이 떠올랐고, 그 문제에서 DP를 요구하는 것도 알았으나 DP 를 잘 못해서 풀 수 없었다고 ....

DP 유형을 게을리 하지 말자.

하루에 백준 1문제 이상 푸는 것을 목표로 하고 있다.
https://solved.ac/profile/anwlro0212