문제

BOJ 15486, 퇴사 2

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• N + 1일째 되는 날 퇴사를 하는데, 남은 N일 동안 상담을 하고 얻을 수 있는 최대 수익을 구해야 한다.
• 문제 지문 설명만으론 N + 1일날 상담하고 퇴사를 하는지, 바로 퇴사를 하는지 모호하다. 예제 2를 보면 N + 1일에 일을 하고 퇴사한다는 사실을 알 수 있다.
• 날짜별로 상담하거나 안 했을 때 수익을 저장하면 모든 상담을 한 번만 확인하며 최대 수익을 확인할 수 있다.

// dp[i]: i일에 얻을 수 있는 최대 수익
dp[i] = max(dp[i], dp[i - 1]); // 이전까지 최대 수익 선택 
if (i + t[i] <= n + 1)
	dp[i + t[i]] = max(dp[i + t[i]], dp[i] + p[i]); // 현재까지 최대 수익에 상담 수익을 더한 것을 기록

• 이전까지 최대 수익을 저장하고, 현재 시점 상담 수익을 더 큰 것으로 결정하므로 dp[n]에는 n일에 얻을 수 있는 최대 수익이 기록된다. n + 1에 일을 하고 퇴사하는 경우도 있으므로 dp[n]과 dp[n + 1] 중 최댓값을 출력하면 된다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
using namespace std;

int t[1'500'004];
int p[1'500'004];
int dp[1'500'004];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> t[i] >> p[i];
	for (int i = 1; i <= n; ++i) {
		dp[i] = max(dp[i], dp[i - 1]);
		if (i + t[i] <= n + 1)
			dp[i + t[i]] = max(dp[i + t[i]], dp[i] + p[i]);
	}
	cout << max(dp[n], dp[n + 1]);
}

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] t = new int[n + 4];
        int[] p = new int[n + 4];
        int[] dp = new int[n + 4];
        for (int i = 1; i <= n; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 1; i <= n; ++i) {
            dp[i] = Math.max(dp[i], dp[i - 1]);
            if (i + t[i] <= n + 1)
                dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
        }
        System.out.println(Math.max(dp[n], dp[n + 1]));
        br.close();
    }
}