백준 15486 JAVA : 퇴사 2

문제

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

 

풀이 예상

N의 범위가 150만 이므로 N이 15개 이하인 퇴사 문제는 완탐으로 풀 수 있었지만 퇴사 2는 완탐으로 불가능 하다.

그렇기 때문에 dp를 사용했다.

 

 

풀이방법 (접근 방법 & 시간복잡도)

dp배열의 의미는 해당 인덱스 시간에 최대 금액을 의미한다.

각 인덱스에서 해주어야 할 것은

1. 이전 시간에서의 최대 금액 가져오기

2. 인덱스 시간부터 -50 시간까지 탐색을 하며 지금 인덱스 시간에서 끝나는 상담인 경우

    그 상담의 비용 + 그 상담 받기 전 최대 금액 과 현재 시간 최대값 갱신

=> -50시간인 이유는 문제에서 T의 범위가 1 ≤ T ≤ 50 이기 때문

 

시간복잡도 => O(N)

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] counsel = new int[N+1][2]; //0:시간, 1:금액
        int[] dp = new int[N+1]; //index 시간에 최대 금액
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            counsel[i][0] = Integer.parseInt(st.nextToken());
            counsel[i][1] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= N; i++) {
            dp[i] = dp[i-1];
            for (int j = i; j >= Math.max(0, i - 50); j--) {
                if(i == j + counsel[j][0] -1) { //i 시점에 끝나는 상담인 경우
                    dp[i] = Math.max(dp[i], counsel[j][1]+ dp[j-1]);
                }
            }

        }

        System.out.println(dp[N]);

    }
}

결과