[JAVA] BOJ 14501 퇴사 DP

문제 설명

일할 수 있는 요일을 지정해서 최대 요금을 구해야 하는문제
여러 방법을 생각했는데, 가장 효율적인 방법은 아니게 풀었다.
방법 1. 이중 for문
방법 2. 완전 DP

풀이

내 풀이

해당 날짜가 되면 그 날짜에 도달할 수 있는 경우의 수가 있는지 for문으로 탐색한다. 시간복잡도가 그렇게 크지 않아서 가능했던 풀이 방식이다.

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

class Main {
    static int N;
    static int[][] arr;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1][2];
        dp = new int[N + 1];

        StringTokenizer st;
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= N; i++) {
            int maxDp = dp[i-1];
            for(int j = 1; j <= i; j++) {
                if(i == (j + arr[j][0] - 1)) {
                    maxDp = Math.max(maxDp, dp[j-1] + arr[j][1]);
                }
            }
            dp[i] = maxDp;
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
    }
}

 

다른 사람 풀이

두 번의 계산이 필요하다.

1. arr[i]에 진행한 상담이 며칠 뒤에 돈을 버는지
2. 오늘 일한 걸 다음날 누적시킨다.

핵심 계산식은 아래와 같다.

dp[i+t[i]] = Math.max(dp[i+t[i]], dp[i] + p[i]);

오늘 일한거 + 지금까지 모인거 vs 해당 날짜에 이미 누적되어있는 값

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));

       int N = Integer.parseInt(br.readLine());

       int[] t = new int[N];
       int[] p = new int[N];

        StringTokenizer st;

        for(int i=0; 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+1]; // 1일에 일한 돈은 2일차에 누적되기 때문
         // 날짜를 진행하면서 해당 날짜에 대한 최대 요금을 저장하는 배열, 각 배열의 인덱스마다 최대 요금을 저장해놓는다. 

        for(int i=0; i<N; i++){
            if(i + t[i] <= N) { 
                // 날짜가 초과되지 않으면서 해당 날짜에 번 돈을 계산
                dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
            }

            // 오늘 일한 걸 다음날 누적시키기 위한 계산
            dp[i+1] = Math.max(dp[i+1], dp[i]);
        }
        System.out.println(dp[N]);
    }
}