[알고리즘]퇴사

package org.example.퇴사;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.text.MessageFormat;
import java.util.Arrays;
import java.util.Objects;

public class Main {
    public static void main(String[] args) {
        try (
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ) {
            int N = Integer.parseInt(br.readLine());
            
            if (!(1 <= N && N <= 15)) {
                String errorMessage = MessageFormat.format("N은 1 이상 15 이하의 정수여야 합니다. N = {0}", N);
                throw new IllegalArgumentException(errorMessage);
            }
            
            Work[] works = new Work[N];
            
            for (int i = 0; i < N; i++) {
                String[] input = br.readLine()
                                   .split(" ");
                Work work = Work.of(input[0], input[1]);
                works[i] = work;
            }
            int[] dp = new int[N + 1];
            for (int i = 0; i < N; i++) {
                Work todayWork = works[i];
                int todayWorkEndDay = i + todayWork.getT();
                int todayWorkProfit = todayWork.getP();
                if (todayWorkEndDay <= N) {
                    dp[todayWorkEndDay] = Math.max(dp[todayWorkEndDay], dp[i] + todayWorkProfit);
                }
                dp[i+1] = Math.max(dp[i+1], dp[i]);
            }
            System.out.println(dp[N]);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    
    public static class Work {
        private final int t;
        private final int p;
        
        public Work(int t, int p) {
            if (!(1 <= t && t <= 5)) {
                throw new IllegalArgumentException(MessageFormat.format("t는 1 이상 5 이하여야 합니다. t = {0}", t));
            }
            if (!(1 <= p && p <= 1000)) {
                throw new IllegalArgumentException(MessageFormat.format("p는 1 이상 1,000 이하여야 합니다. p = {0}", p));
            }
            this.t = t;
            this.p = p;
        }
        
        public static Work of(String otherT, String otherP) {
            Objects.requireNonNull(otherT, "otherT는 null이 아니어야 합니다.");
            Objects.requireNonNull(otherP, "otherP는 null이 아니어야 합니다.");
            int t = Integer.parseInt(otherT);
            int p = Integer.parseInt(otherP);
            
            return new Work(t, p);
        }
        
        public int getT() {
            return t;
        }
        
        public int getP() {
            return p;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Work)) return false;
            
            Work work = (Work) o;
            
            if (t != work.t) return false;
            return p == work.p;
        }
        
        @Override
        public int hashCode() {
            int result = t;
            result = 31 * result + p;
            return result;
        }
        
        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Work{");
            sb.append("t=")
              .append(t);
            sb.append(", p=")
              .append(p);
            sb.append('}');
            return sb.toString();
        }
    }
    
}

• dp는 쉬운 문제더라도 감이 잘 안잡히는거 같다.

if (todayWorkEndDay <= N) {
  dp[todayWorkEndDay] = Math.max(dp[todayWorkEndDay], dp[i] + todayWorkProfit);
}

• 하루씩 순회하면서

• dp[현재 상담을 받는다면 끝나는 일자] = (dp[현재 상담을 받으면 끝나는 날짜] 최대이익 , 현재 최대 이익 + 상담에 대한 이익)

• 중에 큰 값을 세팅해준다.

dp[i+1] = Math.max(dp[i+1], dp[i]);

• 다만, 놓치면 안되는 부분은 dp 배열의 이익값 자체는 전부 0 으로 초기화가 되어있기에, 다음 최대 이익은 항상 이전 최대 이익을 보장해야한다.

Uploaded by N2T