[백준] 14501 퇴사 (Java)

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

 

집중력 최하로 떨어진 날...

어려운 문제도 아니고 같은 유형의 문제를 풀어본 기억이 있는데도 불구하고
한번에 풀지 못한게 너무 아쉽다

짧게 요약만 하고 내일 일어나서 다시 풀려고 한다

다시 풀어보니 전혀 다른 경험치를 쌓을 수 있는 문제라 생각되서 정리를 다시 한다

dp의 개념을 새로 정립한 느낌이다

n = dp(n - 1) + dp(n - 2) 와 같은 점화식은 익숙하다

하지만 선택해야 하는 범위가 상수를 연산하는 것 만으로 표현 할 수 없는 경우에 대해서는 생각해 보지 않았다

이번 문제에서는 현재 회의를 했을 때 (p[i] + dp[i]) 와 하지 않고 그 날짜만큼 지났을 때의 값(dp[t[i] + i])

중에 큰 것을 dp[t[i] + i]에 저장하는 것이 답 이었다

이 처럼 dp 알고리즘에서 표현하는 범위가 더 복잡할 수 있다는 것을 배운 좋은 문제였다


dp의 인덱스로 t[i]를 사용하는 것에 대한 이해는 부족하여 완전히 이해하지 못했지만,

더 많은 문제를 풀다보면 언젠가 이해하는 날이 오겠지

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

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 max = 0;
        int[] t = new int[n + 1];
        int[] p = new int[n + 1];
        int[] dp = new int[n + 15];
        
        for(int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = 0; i <= n; i++){
            dp[i] = Math.max(max, dp[i]);
            
            dp[t[i] + i] = Math.max(dp[t[i] + i], p[i] + dp[i]);
            
            max = Math.max(dp[i], max);
        }
        
        System.out.println(max);
    }
}

(어째선지 백준에 풀었던 기록이 남아있지 않아서 코드 증발)
백트래킹 코드이다

상담 시간과 상담 비용 두가지가 있어서 map을 써야하나 싶지만, 굳이 그럴 필요 없다
(실제로 map을 쓰면 key를 출력할 방법이 없어 key와 value를 뒤바꿔서 두번 해야할 번거로움이 있을듯)

그냥 배열을 이중 배열로 하여 [n][2] 로 0은 회의시간, 1은 val로 사용하면 된다

dfs로 인자는 idx, pay 두개를 0, 0 으로 받는다

idx >= N 이 된다면 Math.max(pay, result)를 result 에 담고 리턴

범위는 idx + arr[idx][0] 이 n보다 작거나 같은 경우

dfs -> idx + arr[idx][0] 을 idx로, pay + arr[idx][1] 을 pay로 보내 재귀한다
(idx는 현재 시간 + 이번 회의 진행 시간, pay는 현제 pay + 이번 회의 비용)

회의를 진행 할 수 없다면(else) 위처럼 회의 시간만 더하고 pay는 그대로

빠져나온 뒤에

상담하지 않고 다음 상담하는 경우도 구하기 위해 dfs(idx + 1, pay)


일어나서 자력으로 dp코드로 변형하여 짜 봤는데, nullpoint 에러를 해결하지 못했다