[백준] 14501번 퇴사

1) 생각

기간 N이 주어지고 N일동안 날마다 할 상담의 보수와 상담에 걸리는 시간이 주어질 때, 최대 보수를 구하는 문제이다.

이전에 SW Expert Academy에서 풀었던 [SW Expert] 5215번 햄버거 다이어트 문제와 유사하다.

다른 점이 있다면 시간을 신경써줘야 한다는 점이다.

2) 방안

해당 날짜에 상담을 시작하면 주어진 시간 만큼 상담을 하지 못하므로 Index 번호를 해당 날짜에 주어진 상담 기간 만큼 늘려주어 해결하였다.

import java.io.IOException;
import java.util.Scanner;
 
public class Main{
    static int n;
    static int[] time,value;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        time = new int[n];
        value = new int[n];
        for(int i=0;i<n;i++) {
            time[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        max = Integer.MIN_VALUE;
        solve(0,0);
        System.out.println(max);
    }
    
    static int max;
    private static void solve(int idx,int v) {
        if(idx>n) return;
        if(idx==n) {
            max = Math.max(max, v);
            return;
        }        
        // 현재 idx를 포함 => 상담 못하는 시간만큼 idx를 올려줌
        solve(idx+time[idx],v+value[idx]);
        // 현재 idx를 미포함
        solve(idx+1,v);
    }
}