[java]백준 14015번 퇴사

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

14501번: 퇴사

 

 

문제 요약

 

N+1일째 되는 날 퇴사를 한다.

상담 일정이 상담이 걸리는 기간 T 과 받을 수 있는 금액 P 이 주어진다.

상담을 선택해서 했을 때 받을 수 있는 최대 금액

 

---

사용한 알고리즘

 

DP(Dynamic Programming)

 

---

풀이

 

1. 

int [][] plan=new int[N+1][2]; // 1일부터 N일까지 확인위해 N+1
for(int i=1; i<N+1; i++){
    st=new StringTokenizer(br.readLine());
    plan[i][0]=Integer.parseInt(st.nextToken());
    plan[i][1]=Integer.parseInt(st.nextToken());
}

plan이라는 이차원 배열에 

p[i][0]: i날의 상담에 걸리는 시간, p[i][1]: i날의 상담 후 받을 수 있는 금액을 넣어줬다.

 

 

2.  D 점화식 

 

• T: 상담 시간, P: 상담 금액
• D[i]: i날까지의 최대 수익
• N+1일에 퇴사하므로 int D []=D [n+2]로 초기화해줌.

-> 퇴사하는 N+1을 신경 써줘야 한다!( 마지막 날인 N인 날 하루 상담이었을 때를 위해서)

1) i 날의 상담을 들었을 때 i날에 상담기간 T를 더한 날 값을 확인해 준다

 D [i+T] i+T날의 최대수익과 i날 상담을 들었을 때 받을 수 있는 수익 D [i]+P를 비교해서 큰 값 넣어준다.

// i일의 상담을 들었을 때
// D[i+T]=D[i+T]와 오늘까지의 최대값 D[i]+P 비교해서 큰 값 넣어주기
D[i+T]=Math.max(D[i+T],D[i]+P);

 

2) 항상 i 날 D [i]까지의 최대수익을 다음날 D [i+1]에 넣어준다.

D [i+T] i+T날의 최대수익과 D [i] i날까지의 최대 수익을 비교해서 큰 값을 넣어준다.

// i+1날의 값에 i+1날의 최대 수익과 오늘까지의 최대 수익 비교해서 넣어주기
D[i+1]=Math.max(D[i+1],D[i]);

 

위의 점화식을 아래 반복문에서 돌려준다. 

• 1일부터 N일까지 반복문을 돌며( i날에 상담을 들었을 때 i + T가 퇴사날짜 전에(<N+1))

for(int i=1; i<N+1; i++){
            int T=plan[i][0]; // i일 상담의 걸리는 시간
            int P=plan[i][1]; // i일 상담의 금액

            if(i+plan[i][0]<=N+1){ // 오늘 상담이 퇴사 전까지 끝나는지 확인
                // i일의 상담을 들었을 때
                // D[i+T]=D[i+T]와 오늘까지의 최대값 D[i]+P 비교해서 큰 값 넣어주기
                D[i+T]=Math.max(D[i+T],D[i]+P);
            }
            // i+1날의 값에 i+1날의 최대 수익과 오늘까지의 최대 수익 비교해서 넣어주기
            D[i+1]=Math.max(D[i+1],D[i]);
        }

 

3.  D [N+1]에는 최대수익이 들어있으므로 답은 D[N+1]

 

---

코드

 

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

public class 백준_퇴사 {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int N=Integer.parseInt(st.nextToken()); // 퇴사 전까지 남은 N일
        // 상담 일정표 plan[i][0]: i일 상담의 걸리는 기간 T, plan[i][1]: i일 상담의 금액 P
        int [][] plan=new int[N+1][2]; // 1일부터 N일까지 확인위해 N+1
        for(int i=1; i<N+1; i++){
            st=new StringTokenizer(br.readLine());
            plan[i][0]=Integer.parseInt(st.nextToken());
            plan[i][1]=Integer.parseInt(st.nextToken());
        }

        int D[]=new int[N+2]; // 다이나믹 프로그래밍 사용, i일까지의 최대 수익, N+1일(퇴사까지 비교)
        for(int i=1; i<N+1; i++){
            int T=plan[i][0]; // i일 상담의 걸리는 시간
            int P=plan[i][1]; // i일 상담의 금액

            if(i+plan[i][0]<=N+1){ // 오늘 상담이 퇴사 전까지 끝나는지 확인
                // i일의 상담을 들었을 때
                // D[i+T]=D[i+T]와 오늘까지의 최대값 D[i]+P 비교해서 큰 값 넣어주기
                D[i+T]=Math.max(D[i+T],D[i]+P);
            }
            // i+1날의 값에 i+1날의 최대 수익과 오늘까지의 최대 수익 비교해서 넣어주기
            D[i+1]=Math.max(D[i+1],D[i]);
        }
        // 퇴사날의 최대값 출력!
        System.out.println(D[N+1]);
    }
}