14501. 퇴사

문제 개요

다이나믹 프로그래밍을 이용한 스케쥴링 문제입니다.

문제 접근

간단한 문제였는데, 생각을 잘못해서 조금 오래 걸렸습니다.
작업이 진행되는 기간이 주어지기 때문에 이를 고려해서 프로그래밍 해야 합니다. A 상담이 끝나는 시점부터 마지막날까지 최고점이 갱신되어야 했는데, 이 점을 적용하지 않아서 자꾸 틀렸습니다.

N값이 작기 때문에 그냥 브루트포스로 풀어도 될 것 같습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Pair{
    private int duration;
    private int cost;

    public Pair(String ab){
        String[] abs = ab.split(" ");
        duration = Integer.parseInt(abs[0]);
        cost = Integer.parseInt(abs[1]);
    }

    public Pair(int duration, int cost){
        this.duration = duration;
        this.cost = cost;
    }

    public int getDuration() {
        return duration;
    }

    public void setDuration(int duration) {
        this.duration = duration;
    }

    public int getCost() {
        return cost;
    }

    public void setCost(int cost) {
        this.cost = cost;
    }


}

public class Main {
    static int N;
    static Pair[] p;
    static void input() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        p = new Pair[N];
        for(int i=0;i<N;i++){
            p[i] = new Pair(bf.readLine());
        }
    }

    static void process(){
        int[] memo = new int[N+1];

        for(int i=0;i<N;i++){
            int next = i + p[i].getDuration();
            for(; next<=N;next++){
                memo[next] = Math.max(memo[next], memo[i]+p[i].getCost());
            }
        }
        System.out.println(Arrays.stream(memo).max().getAsInt());
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

문제

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