[백준/JAVA] 14501번: 퇴사

🔺 문제

14501번: 퇴사

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int[] D = new int[N + 2];   // 오늘~퇴사일까지 벌 수 있는 최대 수입
        int[] T = new int[N + 1];   // 상담에 필요한 일 수
        int[] P = new int[N + 1];   // 상담 완료 시 받는 수입 저장 배열
        
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = N ; i > 0 ; i--) {
            // i번째 상담을 퇴사일까지 끝낼 수 있을 때
            if((i + T[i] - 1) <= N) {
                D[i] = Math.max(D[i + 1], D[i + T[i]]) + P[i]);
            }
            // i번째 상담을 퇴사일까지 끝낼 수 없을 때, 수입은 그대로
            else {
                D[i] = D[i + 1];
            }
        }
        System.out.println(D[1]);
    }
}

✅ 해결 아이디어
✔ DP - 점화식
→ dp[N] : N일에 얻을 수 있는 최대 수익

 

---

🔺 다른 풀이들

- 점화식이 약간 다르다. (DP 배열을 앞에서부터 채움)

[알고리즘/백준] 14051 퇴사 - 자바(Java), DP, 삼성 SW 역량테스트 기출

[백준 14501] 퇴사 (자바)

 

 

- 2차원 배열 점화식 & 재귀를 사용하셨다.

백준 14051 - 퇴사 · Yesdoing의 개발 블로그

---

💬 느낀 점

재귀를 잘하고 싶구나...

 

 

1회독	2회독	3회독	4회독	5회독
V	7/5

 

 

(+7/3 2회독)

나름 점화식 비슷하게 쓴 거 같은데... 은근(?) 틀림

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        
        int[] D = new int[N + 2];
        int[][] arr = new int[N + 1][2];
        
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = N ; i > 0 ; i--) {    // 뒤에서부터 거꾸로~
            if(i + arr[i][0] - 1 <= N) {
                D[i] = Math.max(D[i+1], arr[i][1] + D[i + arr[i][0]]);
            }
            else {
                D[i] = D[i + 1];
            }
        }
        System.out.println(D[1]);
    }
}
 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편