[DP] 퇴사

백준 14501 퇴사 (삼성 SW역량테스트 기출)

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

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

public class Main {

    static int N;
    static Work[] works;
    static int[] D; //n일까지 벌수 있는 최대 금액

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        works = new Work[N+1];
        D = new int[N+1];

        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            int money = Integer.parseInt(st.nextToken());
            works[i] = new Work(time, money);
        }

        System.out.println( dp(0,0) );
    }


    //bottom-up
    static int dp(int date, int money){

        D[date] = Math.max( D[date], money);

        //종결
        if(date==N){ return D[date]; }

        int t = works[date+1].time;
        int m = works[date+1].money;

        if(date+t<=N){
            return Math.max( dp(date+1, D[date]), dp(date+t, D[date]+m )); //Max(오늘일하기, 다음날확인)
        }else{
            return dp(date+1, D[date]); //다음날확인
        }
    }


    static class Work{
        int time;
        int money;

        Work(int time,int money){
            this.time = time;
            this.money = money;
        }
    }
}

개선하기

D[date] = Math.max( D[date], money);

if(D[date] <= money) D[date]=money;
else return -1;

어자피 안될놈들은 일찌감치 포기

틀렸던 부분

if(date==0 || D[date] < money) D[date]=money;
else return -1;

개선할 때 <=가 아니라 <면 틀림. 

등호를 빼면 다음날을 도모하기 위해 알안하고 간보러 온 애(money=0)들의 싹을 피워보지도 못하고 짖밟아버리게 됨.