[백준] 퇴사 Java

퇴사

완전 탐색을 해야 하는 문제입니다.

일을 한 날과 안한 날을 모두 계산해야 최대값을 얻을 수 있습니다.
완전 탐색을 하면 데이터의 중복이 생기기 때문에, (ex 피보나치 수열)
데이터를 배열에 저장해서 꺼내쓰는 방식의 dp를 사용하면 O(n)으로 끝낼 수 있습니다.

재귀를 사용한 풀이 방법

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

public class Main {
    public static int N;
    public static int answer = Integer.MIN_VALUE;
    public static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        solve(0, 0);

        System.out.println(answer);

    }

    private static void solve(int current, int rsl) {
        if(current == N){
            answer =  Math.max(rsl, answer);
            return;
        }
        if(current > N) return;

        int day = arr[current][0];
        int money = arr[current][1];

        //일 한 경우
        solve(current+day, rsl + money);
        //일 안한 경우
        solve(current+1, rsl);
    }
}

dp를 사용한 풀이 방법

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] T = new int[N];
        int[] P = new int[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        //수익 저장
        int[] memorize = new int[N+1];

        for(int i = 0; i < N; i++){
            if(i + T[i] <= N){
                memorize[i + T[i]] = Math.max(memorize[i + T[i]], memorize[i] + P[i]);
            }
            memorize[i+1] = Math.max(memorize[i + 1], memorize[i]);
        }

        System.out.println(memorize[N]);

    }
}