[BOJ] 14501번 퇴사

문제

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

14501번: 퇴사

 

풀이

이 문제 또한 전형적인 모든 경우의 수 문제이다. 날짜 시작점에 따라서 주어진 N을 넘지 않는 선에서 재귀를 이용해서 Max값을 계속 갱신해주면서 발생하는 최대의 비용 값을 구하도록 구현했다.

처음에는 이중 for문을 통해서 구하려고 했지만 반복문에 사용되는 첨자 변수를 사용하면 안되는 것인지 몰라도 C++이나 자바에서 증감을 해주지 못했다. 이 측면은 다시 알아보고 공부해야겠다.

 

import java.util.*;
 
class Consulting {
    int time, pay;
 
    public Consulting(int time, int pay) {
        this.time = time;
        this.pay = pay;
    }
}
 
public class Main {
    static Scanner scan = new Scanner(System.in);
    static int N, Max = 0, m_max = 0;
    static Vector<Consulting> plan;
 
    static void init() {
        int t, p;
        N = scan.nextInt();
        plan = new Vector<Consulting>();
        for (int i = 0; i < N; i++) {
            t = scan.nextInt();
            p = scan.nextInt();
            plan.add(new Consulting(t, p));
        }
    }
 
    static void cal_max(int day) {
        Max = Math.max(Max, m_max);
        for (int i = day; i < N; i++) {
            if (i + plan.get(i).time > N)
                continue;
            m_max += plan.get(i).pay;
            cal_max(i + plan.get(i).time);
            m_max -= plan.get(i).pay;
 
        }
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        init();
        cal_max(0);
        System.out.println(Max);
    }
}