1257번: 엄청난 부자

https://www.acmicpc.net/problem/1257


$\sum_{i=1}^n {A[i]*B[i]} = M (B[i]>=0)$을 만족할 때 $\sum_{i=1}^n {B[i]}$의 최댓값을 구하는 문제이다.
A[1..n]에서 A[n](=L)이 가장 크고 일단 B[n]<0이어도 된다고 하자.
어떤 k에 대해 $\sum_{i=1}^{n-1} {A[i]*B[i]} = k (mod L)$을 만족하는 $\sum_{i=1}^{n-1} {B[i]}$의 최솟값을 구해놓았다면 여기에 L짜리 동전을 x개 추가함으로써 $\sum_{i=1}^{n-1} {A[i]*B[i]} = Lx + k$ 꼴의 $\sum_{i=1}^n {B[i]}$ 최솟값을 모두 알아낼 수 있다.

문제는 x = $[M/L]$, k = M%L일 때를 구하는 것이다.

이를 이용하기 위해 L로 나눈나머지로 가능한 k = 0..L-1에 대한 노드를 만들고, 각 동전의 추가에 따라 간선을 추가한다.
i번 노드와 가치가 t인 동전에 대해
i+t < L인 경우, 단순이 t짜리 동전을 하나 추가한다는 의미에서 i -> i+t, 가중치 1인 간선을 만든다.
i+t >= L인 경우, L짜리 동전을 하나 없애고 t짜리 동전을 하나 추가한다는 의미에서 i -> i+t-L, 가중치 0인 간선을 만든다.
모든 노드와 간선을 만든 후 0에서 M%L까지의 최단 거리를 구한다. 이 값 + $[M/L]$이 답이다.

처음으로 돌아와서 B[n]<0인 경우가 과연 존재할까?
최단경로는 길어야 L-1이므로 M%L을 만들기 위해 제거한 L짜리 동전은 많아야 L-1개이다.
그런데 입력으로 주어지는 M은 10억 이상, L은 10000이하이므로 $[M/L] >= 10^6 > 9999 = L-1$.
고로 주어진 입력에 따라 본 알고리즘을 통해 구한 답은 항상 B[n]>=0이다.

아래 소스는 $O(nL\lg {nL})$

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
long long m;
int n, s, a[1000], dp[10000];
int main() {
    scanf("%lld%d", &m, &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    s = *max_element(a, a + n);
    for (int i = 1; i < s; i++) dp[i] = 1e9;
    priority_queue<pair<int, int> > pq;
    pq.push({ 0,0 });
    while (!pq.empty()) {
        int tdis = -pq.top().first, tpos = pq.top().second;
        pq.pop();
        if (dp[tpos] ^ tdis) continue;
        for (int i = 0; i < n; i++) {
            int t = tpos + a[i];
            if (dp[t%s] > tdis + 1 - t / s) {
                dp[t%s] = tdis + 1 - t / s;
                pq.push({ -dp[t%s],t%s });
            }
        }
    }
    printf("%lld", dp[m%s] + m / s);
    return 0;
}