[백준 14501 / JAVA] 퇴사

 

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

14501번: 퇴사

처음에 문제를 읽었을 때 DP만 잘 사용하면 바로 풀 수 있을것 같아 시도해 봤지만 실패..

결국 DP와 브루트포스를 함께 이용했다.

 

간단히 첫 상담 날부터 시작해 해당 날의 상담을 하는 경우와 안하는 경우를 나누어 재귀 호출했다.

 

 

    public static void BP(int total, int index) {
        if (total > result) result = total;
        if (index >= N) return;

        if (index + T[index] - 1 < N) //해당 날짜 상담 하는 경우
            BP(total + P[index], index + T[index]);

        if (index + 1 < N) //하지 않는 경우
            BP(total, index + 1);
    }

최대 금액을 result에 저장한다.

해당 날짜를 상담한다면 해당하는 금액을 total에 넣어주고 index를 상담일수 만큼 더해준다.

 

잘보면 조건문에는 1을 뺀 후 N와 비교한다. 1을 빼는 이유는 당일에 해당하는 일 수를 빼주기 위해서 이다.

쉽게 말해, 상담일수가 1일이라면 그 날에 바로 끝날 수 있기 때문이다.

 

상담을 하지 않는 경우는 total을 증가시키지 않고 다음날로 넘어간다.

 

index가 N보다 크거나 같다면 반환해주는 이유는 마지막 상담의 일수가 1일이고 해당 상담을 한다면

인덱스가 넘어가게 된다.

예를 들어, 총 7일의 상담일 중 7일 날 상담의 일수가 1일이라면 8일로 넘어오게 된다.

이런 경우를 처리해주기 위한 코드이다.

 

반응형

 

전체 코드

import java.util.Scanner;

public class Main {
    static int N, result = 0;
    static int[] T, P, DP;

    public static void BP(int total, int index) {
        if (total > result) result = total;
        if (index >= N) return;

        if (index + T[index] - 1 < N) //해당 날짜 상담 하는 경우
            BP(total + P[index], index + T[index]);

        if (index + 1 < N) //하지 않는 경우
            BP(total, index + 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        T = new int[N];
        P = new int[N];
        DP = new int[N];
        for (int i = 0; i < N; i++) {
            T[i] = sc.nextInt();
            P[i] = sc.nextInt();
        }
        BP(0, 0);

        System.out.println(result);
    }
}