21.05.21 - [BOJ] 14501. 퇴사

[suhyunsim]

문제

• 14501

핵심 아이디어

브루트포스로 풀이

• go(day, sum)
  • day일에 있는 상담을 할 지 말 지 결정
  • 지금까지 얻은 수익: sum
  • 1일 ~ n일이면 편하니까 하나씩 1 더해서 작성
  • 정답 찾음: day == n + 1
  • 불가능: day > n + 1
  • 상담 O: go(day + t[day], sum + p[day])
  • 상담 X: go(day + 1, sum)
• O(2^n)

DP로 풀이

• 작은 문제의 정답이 언제 구해도 같고 작은 문제로 큰 문제를 구할 수 있을 때 브루트포스를 DP로 풀 수 있음
• 작은 문제의 최대값만 알아놓고 그 다음 날짜부터 구하면 됨(작은 문제 영향 X)

어려운 점, 실수

풀이

브루트포스

package main.java.com.poogle.BOJ.Q14501;

import java.util.Scanner;

public class Main {
    static int[] t;
    static int[] p;
    static int n;
    static int ans = 0;

    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);
    }

    private static void go(int day, int sum) {
        if (day == n + 1) {
            if (ans < sum) ans = sum;
            return;
        }
        if (day > n + 1) {
            return;
        }
        go(day + t[day], sum + p[day]);
        go(day + 1, sum);
    }
}

DP

• 똑같고 go()에서 한 부분만 수정

    private static void go(int day, int sum) {
        if (day == n + 1) {
            if (ans < sum) ans = sum;
            return;
        }
        if (day > n + 1) {
            return;
        }
        int t1 = go(day + 1);
        int t2 = p[day] + go(day + t[day]);
        d[day] = Math.max(t1, t2);
        return d[day];
//        go(day + t[day], sum + p[day]);
//        go(day + 1, sum);
    }