BOJ 23933 - Energy Stones 링크
(2024.04.25 기준 P3)

문제

$N$개의 마법의 돌이 주어진다. $i$번째 돌을 먹기 위해선 $S_i$초가 걸린다. 또한 $i$번째 돌의 에너지는 처음에 $E_i$만큼 있으며, $1$초가 지날 때마다 $L_i$ 에너지가 감소한다.
마법의 돌을 먹는 그 순간 그 돌의 현재 에너지를 전부 얻을 수 있게 된다. 최대로 얻을 수 있는 에너지 출력

알고리즘

그리디로 접근해서 돌을 정렬하고 냅색 dp

풀이

$i$번째 돌과 $j$번째 돌을 전부 먹을 수 있다고 가정했을 때, 순서는 어떻게 정해질까?
현재 흐른 시간을 $t$라고 하자.
$i$번째 돌을 $j$번째 돌보다 먼저 먹게 된다면, $E_i - t \times L_i + E_j - (t + S_i) \times L_j$의 에너지를 얻을 수 있다.
$j$번째 돌을 $i$번째 돌보다 먼저 먹게 된다면, $E_j - t \times L_j + E_i - (t + S_j) \times L_i$의 에너지를 얻을 수 있다.
두 식을 정리해서 $i$번째 돌을 $j$번째 돌보다 먼저 먹는 조건은 $\frac{S_i}{L_i} \le \frac{S_j}{L_j}$가 된다. 그러므로 각 돌마다 $\frac{S}{L}$를 구해 이 값으로 정렬하면, 돌들을 먼저 고려해야 하는 순서가 된다.

$dp(i, j)$를 $t = j$일 때 $[i, N-1]$ 구간의 돌을 순서대로 선택할 때의 최적값이라고 정의하자. (0-based index)
$[0, N-1]$ 구간의 돌을 어떤 순서로 고려했든 어떤 돌들을 선택하지 않았든 상관없이, $dp(i,j)$에 영향을 주지 않는다.
그러므로 $i$번째 돌을 선택하지 않거나 선택하거나 둘 중 하나인 점화식인 knapsack, 작은 문제를 먼저 해결해 큰 문제를 해결하는 top-down dp를 같이 이용할 수 있게 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef tuple<int, int, int, double> stone;

vector<stone> stones;
int N, dp[100][10000];

bool comp(stone a, stone b){
    return get<3>(a) < get<3>(b);
}

int dfs(int i, int j){
    if (i == N) return 0;
    if (~dp[i][j]) return dp[i][j];

    // 선택하지 않거나 선택하거나 둘 중 하나다.
    auto [S, E, L, _] = stones[i];
    dp[i][j] = max(dfs(i + 1, j), dfs(i + 1, j + S) + E - L * j);
    return dp[i][j];
}

int solve(){

    // i, j번 돌 중 고려해야 하는 순서를 정해보자.
    // i를 j보다 먼저 선택하게 된다면, Ei - tLi + Ej - (t + Si)Lj
    // j를 i보다 먼저 선택하게 된다면, Ej - tLj + Ei - (t + Sj)Li
    // i를 j보다 먼저 선택하는 조건은 Si/Li <= Sj/Lj
    // 그러므로 각 돌마다 S/L을 구해서 정렬을 하면 된다.
    cin >> N; stones.clear();
    for (int i = 0, S, E, L; i < N; i++){
        cin >> S >> E >> L;
        if (L) stones.push_back({S, E, L, (double)S / L});
        else stones.push_back({S, E, L, 101}); // L = 0을 주의하자.
    }
    sort(stones.begin(), stones.end(), comp);
    
    // 고려해야 하는 순서가 정해졌다면, 앞 순서의 돌부터 냅색 dp를 진행하면 된다.
    // 남은 돌이 같다면, 어떤 순서로 돌들을 선택해왔든 현재 흐른 시간은 같으므로
    // 남은 돌들의 최적값은 동일하다.
    // 그러므로 dp를 사용할 수 있다.
    memset(dp, -1, sizeof(dp));
    return dfs(0, 0);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    for (int x = 1; x <= T; x++) cout << "Case #" << x << ": " << solve() << '\n';
}

• Python

import sys; input = sys.stdin.readline

def dfs(i, j):
    if i == N:
        return 0
    if ~dp[i][j]:
        return dp[i][j]

    # 선택하지 않거나 선택하거나 둘 중 하나다.
    S, E, L, _ = stones[i]
    dp[i][j] = max(dfs(i + 1, j), dfs(i + 1, j + S) + E - L * j)
    return dp[i][j]

for x in range(1, int(input()) + 1):

    # i, j번 돌 중 고려해야 하는 순서를 정해보자.
    # i를 j보다 먼저 선택하게 된다면, Ei - tLi + Ej - (t + Si)Lj
    # j를 i보다 먼저 선택하게 된다면, Ej - tLj + Ei - (t + Sj)Li
    # i를 j보다 먼저 선택하는 조건은 Si/Li <= Sj/Lj
    # 그러므로 각 돌마다 S/L을 구해서 정렬을 하면 된다.
    N = int(input())
    stones = []
    for _ in range(N):
        S, E, L = map(int, input().split())
        if L:
            stones.append((S, E, L, S / L))
        else: # L = 0을 주의하자.
            stones.append((S, E, L, 101))
    stones.sort(key = lambda x: x[3])

    # 고려해야 하는 순서가 정해졌다면, 앞 순서의 돌부터 냅색 dp를 진행하면 된다.
    # 남은 돌이 같다면, 어떤 순서로 돌들을 선택해왔든 현재 흐른 시간은 같으므로
    # 남은 돌들의 최적값은 동일하다.
    # 그러므로 dp를 사용할 수 있다.
    dp = [[-1] * 10001 for _ in range(N)]
    print('Case #%d: %d' % (x, dfs(0, 0)))