백준 14501: 퇴사[JAVA]

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

14501번: 퇴사

 

 

[난이도]

- Silver 3

 

[알고리즘]

- 부르트 포스

- dfs

 

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int N, maxPay = Integer.MIN_VALUE;
    static int[][] arr;
    static boolean[] checked;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        arr = new int[N][2];
        checked = new boolean[N];

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

        dfs(0, 0);
        System.out.println(maxPay);

    }

    static void dfs(int index, int pay) {
        if (index >= N) {
            maxPay = Math.max(maxPay, pay);
            return;
        }

        if (index + arr[index][0] <= N) { // 날짜를 초과하지 않는다면
            dfs(index + arr[index][0], pay + arr[index][1]); // 상담을 진행 후의 날짜, 금액을 추가해 넘겨준다
        } else { // 날짜를 초과한다면
            dfs(index + arr[index][0], pay); // 금액을 추가하지않고 넘겨준다, 다음 if문에서 걸리기 때문
        }
        dfs(index + 1, pay); // 완전 탐색하기위한 코드, 0일부터시작, 1일부터 시작, ...
    }
}

 

[풀이]

1. index가 N을 초과할 경우 현재까지 쌓인 pay중의 최대값을 maxPay에 저장한다.

2 - 1. 현재날짜에서 상담 후의 날짜가 N을 초과하지 않는다면 (상담 후의 날짜, 상담 후의 금액)을 넘겨준다.

2 - 2. 현재날짜에서 상담 후의 날짜가 N을 초과한다면(상담 후의 날짜, 상담 전의 금액)을 넘겨준다. 이렇게 하는 이유는 다음 if문에서 걸려 maxPay를 갱신하기 위함이다.

3. 0일째부터 상담 시작했을 경우가 끝났다면, 다시 1일부터 상담 시작했을 경우, 2일부터 상담 시작했을 경우... 로 계속진행한다. N + 1일부터 상담 시작했을 경우까지 갔을 경우 끝난다.