[BOJ/Java] 14501. 퇴사

[BOJ/Java] 14501. 퇴사

14501번: 퇴사

---

문제 해석

"퇴사" 문제는 남은 N일 동안의 상담 스케줄을 고려하여 최대 수익을 얻을 수 있는 방법을 찾는 문제이다. 각 상담은 일정 기간과 해당 기간 동안 얻을 수 있는 금액이 정해져 있으며, 상담은 겹치지 않아야 한다.

풀이 과정

해당 문제를 해결하기 위해 사용된 알고리즘은 동적 프로그래밍(Dynamic Programming)이다. N일 동안 각 날짜에 대해 최대 수익을 저장할 dp 배열을 생성하고, 각 상담의 가능성을 검토하면서 최대 수익을 갱신한다.

 

1. 입력으로 받은 상담 일정을 Consult 배열에 저장한다.
2. dp 배열의 각 원소를 초기화한 후, 각 상담에 대해 상담이 가능한 조건(상담 종료일이 N일을 넘지 않을 때)을 검토한다.
3. 상담이 가능한 경우, dp[i+c.day] (상담 종료일의 수익)을 dp[i] + c.value (시작일의 수익 + 해당 상담 수익)와 비교하여 더 높은 값으로 갱신한다.
4. 모든 날짜에 대해 이러한 과정을 반복하여 dp[N]에서 최대 수익을 도출한다.

코드

package edu.ssafy.im.BOJ.Silver.S3.No14501;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    private static int N; // 상담 가능한 총 일수
    private static Consult[] consultArray; // 상담 일정 배열
    private static int[] dp; // 동적 프로그래밍을 위한 수익 저장 배열

    static class Consult {
        int day, value; // 상담 소요일과 수익

        public Consult(int day, int value) {
            this.day = day;
            this.value = value;
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        N = Integer.parseInt(br.readLine()); // 입력: 전체 상담 가능 일수
        
        consultArray = new Consult[N]; // 상담 일정 배열 초기화
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int day = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            consultArray[i] = new Consult(day, value); // 상담 일정 입력 받기
        }

        dp = new int[N+1]; // 수익 배열 초기화 (+1은 0일차를 고려)
        for (int i = 0; i < N; i++) {
            Consult c = consultArray[i];
            dp[i+1] = Math.max(dp[i], dp[i+1]); // 오늘의 최대 금액 갱신
            if (i+c.day >= N+1) continue; // 상담 종료일이 N+1을 초과하는 경우 무시
            dp[i+c.day] = Math.max(dp[i+c.day], dp[i]+c.value); // 상담 가능한 경우, 상담 종료일의 수익 갱신
        }

        sb.append(dp[N]); // 최대 수익 출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)이다. 각 날짜에 대해 상담의 가능성을 단 한 번씩만 확인하며, 각 확인은 상수 시간 연산을 요구한다.

느낀점

동적 프로그래밍을 통해 이 문제를 해결하는 과정에서, 각 상담의 선택이 후의 결정에 어떻게 영향을 미치는지 체계적으로 분석할 수 있었다. 이러한 접근 방식은 실제 문제 해결 시 매우 유용하게 사용될 수 있다는 점을 깨닫는 계기가 되었다.