[백준] 14501번 퇴사 (Java)

백준 14501번 퇴사 : https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

 

보자마자 DP 문제라고 느낌이 왔지만,

dfs로 더 쉽게 풀 수 있을 듯 해서 dfs로 풀게 되었다.

 

삼성 SW 역량테스트 기출 문제라고 해서 풀어봤는데, 생각보다 너무 쉬워서 깜짝 놀랬다.

 

 

총 걸린 시간 : 20분

난이도 : ★☆☆☆☆

 

코드

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

public class Main {
    private static int n, answer = 0;
    private static int[] T, P;

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

        n = Integer.parseInt(br.readLine());

        T = new int[n];
        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());
        }

        dfs(0, 0);
        System.out.println(answer);
    }

    private static void dfs(int index, int value) {
        if (index >= n) {
            answer = Math.max(answer, value);
            return;
        }

        // 해당 index를 포함
        if (index + T[index] <= n) dfs(index + T[index], value + P[index]);
        else dfs(index + T[index], value); // n을 넘어가면 value 합치지 않음

        dfs(index + 1, value); // 해당 index 미포함
    }
}