BOJ_14501 : 퇴사

👉 문제링크

14501번: 퇴사

---

---

🔸 문제 분석 🔸

• N일동안 업무를 수행한다.
  • N개의 업무의 처리에 필요한 시간 t와 받는 금액 p가 있다.
  • 처리에 필요한 시간이 N일을 넘으면 처리 불가능하다.
  • 받을 수 있는 금액의 최대값을 출력한다.
• 재귀 메소드로 브루트 포스 방식으로 풀이할 수 있다.
• 다이나믹 프로그래밍 방식으로 풀이할 수 있다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] t = new int[n];
        int[] p = new int[n];

        for (int i = 0; i < n; i++) {
            t[i] = sc.nextInt();
            p[i] = sc.nextInt();
        }

        int[] dp = new int[n + 1];

        for (int i = 0; i < n; i++) {
            if (i + t[i] <= n) {
                dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
            }
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);
        }
        System.out.println(dp[n]);
    }
}

🔸 코드 해석 🔸

• dp방식으로 풀이했다. int형 배열 dp는 (인덱스)일에 받을 수 있는 최대 금액을 저장한다.
  • 현재 일(i) + 업무 처리에 필요한 기간( t[ i ] )이 n이하여야 처리 가능한 업무이다.
    • 기존 값 dp[ i + t[ i ] ]와 해당 업무를 처리했을 때 얻는 금액 dp[ i ] + p[ i ] 중 큰 값을 저장한다.
  • 현재 일에 업무를 처리하지 않는 경우도 있다.
    • 다음 일dp[ i + 1 ]에 현재 일dp[ i ]와 비교해서 큰 값을 저장한다.

---

🔸 end 🔸

• 단순 for문으로 구현했을때 예제 4번을 통과하지 못했다.
  • 현재 일에 업무를 처리하지 않는 경우를 빠뜨렸기 때문이다.
• dp로 구현하니 생각보다 문제가 간단해졌다.
  • 예제 4번을 통과하지 못하고 문제의 알고리즘 분류를 봤을때, dp와 Brute Force가 있길래 재귀와 dp배열이라 생각했는데 배열 규칙이 어려울 것이라 겁먹었던 것 같다.
• 삼성 SW 역량 테스트 기출 문제의 최저 난이도 문제이다.