백준 14501 / 퇴사

dogit·2021년 8월 16일

백준 브루트 포스

백준문제

목록 보기

55/67

문제

풀이

설명

N+1일이 되는 날 퇴사를 하려고 한다.
남은 N일동안 최대한 많은 상담을 하려 하며 하루에 하나의 상담을 할 수 있다고 한다.
i일에 상담을 하면, T[i]일이 걸리고 P[i]원을 번다.

코드

import java.util.*;

public class Main {
    static final int inf = -100000000;
    static int[] t;
    static int[] p;
    static int n;
    static int ans = 0;
    static void go(int day, int sum) {
        if (day == n+1) {
            if (ans < sum) ans = sum;
            return;
        }
        if (day > n+1) {
            return;
        }
        go(day+1, sum);
        go(day+t[day], sum+p[day]);
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        t = new int[n+1];
        p = new int[n+1];
        for (int i=1; i<=n; i++) {
            t[i] = sc.nextInt();
            p[i] = sc.nextInt();
        }
        go(1, 0);
        System.out.println(ans);
    }
}