[알고리즘] 백준 14501 : 퇴사 - JAVA

문제

14501번: 퇴사

 

문제이해

백준이는 N+1일째 되는 날 퇴사를 한다. 이를 위해 남은 기간동안 최대한 돈을 벌 예정

각 날짜별로 소요되는 시간과 그에 따른 보상 금액이 주어지고 이를 통해  얻을 수 있는 최대 이익을 구해라

 

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

• N : 남은 날
• Ti : 소요 기간    Pi : 받을 수 있는 금액 (Ti 와 Pi는 공백으로 구분되어 입력)

출력

 

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다

---

풀이

 

완전 탐색을 통해서 풀이할 수도 있지만 dp를 이용하여 풀이 하였습니다

첫날부터 순차적으로 진행하며 현재 + 소요기간이 퇴사날을 넘지 않는다면 현재 + 소요기간의 날에 받을 수 있는 최대 금액을 입력하여 풀이하였습니다

---

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] arg){
        Scanner sc = new Scanner(System.in);
        //  1. 정보 입력 및 초기 세팅
        int n = sc.nextInt();
        int[] days = new int[n];
        int[] price = new int[n];
        int[] dp = new int[n+1];

        for(int i = 0; i < n; i++){
            days[i] = sc.nextInt();
            price[i] = sc.nextInt();
        }
        //  2. dp를 활용하여 날짜별 최대 이익 계산
        for(int i = 0; i < n; i++){
            if(i+days[i] < n+1){
                dp[i+days[i]] = Math.max(price[i]+dp[i], dp[i+days[i]]);
            }
            dp[i + 1] = Math.max(dp[i+1], dp[i]);
        }

        System.out.println(dp[n]);
    }
}