세금 (BOJ 13907번)

문제

이미지 클릭

문제 설명

• 도로를 이동할 때마다 세금을 부가하기 때문에 최소 세금을 지불하는 경로로만 이동해야 함.
• 세금은 특정 금액만큼 상승하기 때문에 그때마다 세금의 최소금액을 얼마 지불해야 하는지 출력해야 함.

문제 해설

문제를 푸는데 두 가지를 고려할 필요가 있음.

• 최소한의 세금을 지불하면서 이동하는 경로가 어떻게 될까?(다익스트라)
• 최소한의 세금을 지불하는 방식을 어떠한 방식으로 저장해야 할까?(다이나믹 프로그래밍)

다익스트라와 같은 경우에는 이전에 하던 것처럼 만들어주면 되지만 만약에 세금이 오르는 것을 업데이트해 주는 과정에서 단순히 전체적인 도로의 세금을 모두 업데이트해주고 다익스트라 알고리즘을 돌린다면 시간초과가 발생하기 때문에 dp를 통해서 새로운 방식으로 세금 금액을 저장해주어야 한다. 

dp [n][m]=k, ( n: 현제 위치, m:현제까지 이동한 도시의 개수, k: 세금 금액 )

 

이러한 방식을 통해서 나중에 세금을 엡데이트를 한다면 dp [n][m]=k+(세금)*m으로 해주면 된다.

 

문제 해설

전체 코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
int n, m, k, a, b;
ll sum;
ll dp[1004][1004];
const ll inf = 1e18 + 4;
vector<pair<ll, ll>> v[30004];
struct P {
    ll c, d, e;
};
void f(int s) {
    queue<P> q;
    q.push({s, 0, 0});
    fill(&dp[0][0], &dp[0][0] + 1004 * 1004, inf);
    dp[s][0] = 0;
    while (!q.empty()) {
        ll x = q.front().c, y = q.front().d, cnt = q.front().e;
        q.pop();
        if (dp[x][cnt] < y) continue;
        for (auto i : v[x]) {
            ll xx = i.first, yy = i.second;
            if (cnt + 1 <= 1003 && dp[xx][cnt + 1] > y + yy) {
                dp[xx][cnt + 1] = y + yy;
                q.push({xx, y + yy, cnt + 1});
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k >> a >> b;
    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }
    f(a); 
    ll mn = inf;
    for (int i = 0; i <= n; i++) mn = min(mn, dp[b][i]);
    cout << mn << "\n";
    while (k--) {
        int x;
        mn = inf;
        cin >> x;
        sum += x;
        for (int i = 0; i <= n; i++) mn = min(mn, dp[b][i] + sum * i);
        cout << mn << "\n";
    }
}

 

 이 코드에서 확인해 볼 부분은 ' 함수 f '이다.

while (!q.empty()) {
  ll x = q.front().c, y = q.front().d, cnt = q.front().e;
  q.pop();
  if (dp[x][cnt] < y)
    continue;
  for (auto i : v[x]) {
    ll xx = i.first, yy = i.second;
    if (cnt + 1 <= 1003 && dp[xx][cnt + 1] > y + yy) {
      dp[xx][cnt + 1] = y + yy;
      q.push({xx, y + yy, cnt + 1});
    }
  }
}

 

• dp [x][cnt]보다 y가 더 큰 경우에는 continue
• 아닐 경우에는 dp [xx][cnt+1]>y+yy, 즉 다음으로 이동할 위치의 세금보다 현제 위치에서의 세금과 다음 위치로 이동하는데 드는 세금이 작다면 세금을 저장해 주고 반복해 준다.

이미지 클릭