백준 14501번 : 퇴사

https://www.acmicpc.net/problem/14501

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

public class Main {
    int[] t;
    int[] p;
    boolean[] visit;
    int n;
    int result = 0;
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        t = new int[n];
        p = new int[n];
        visit = new boolean[n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }
        dfs(0, 0);
        System.out.println(result);
    }
    public void dfs(int index, int sum){
        if(index==n){
            result = Math.max(result, sum);
            return;
        }

        if(index>n) return;

        dfs(index+t[index], sum+p[index]);

        dfs(index+1, sum);
    }



    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

 

완전탐색으로 풀었다. 일을 수행 할 경우와  수행 하지 않았을 경우를 가정해서 탐색을 진행한다. N일에 도달 했을 때 가장 큰 금액을 저장 후 출력한다. DP로도 푸는 방법도 존재한다.