백준 13305번 : 주유소 풀이 (C/C++)

<문제 : 백준 13305번>

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

<풀이>

흔한 dp문제라고 볼 수 있다. 노드의 간선이 2개를 초과하지 않음으로 다익스트라를 사용하지 않아도 된다.

필자는 아래와 같은 점화식으로 구현하였다.

 

 

위 점화식을 그대로 구현하면 아래와 같은데 cost의 범위가 10^9이므로 메모리 초과가 난다.

int dp[101010][1010101010]; //메모리 초과가 남..
int dist[101010], cost[101010];
 
int f(int n, int v){
    if(n == 1){
        return 0;
    }
    if(dp[n][v] != -1) return dp[n][v];
    return dp[n][min(v, cost[n])] = f(n-1, v) + cost[n-1]*dist[n-1];
}

따라서서 findMin함수를 하나 더 구현하여 dp배열의 메모리를 줄였다.

 
ll findMin(int k){ // 1~k까지의 최솟값을 구해주는 함수
    if(k == 1) v[k] = cost[k];
 
    if(v[k] != 0) return v[k];
 
    return v[k] = min(findMin(k-1), cost[k]);
}
 

 

<최종 코드>

구현할때는 오버플로우만 조심하면 된다.

#include<bits/stdc++.h>
#define fio()                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0)
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
const double pi = acos(-1);
const int MOD = 1000000007;
 
typedef tuple<double, int, int> dii;
 
ll dp[101010];
ll dist[101010], cost[101010];
int v[101010];
 
ll findMin(int k){ // 1~k까지의 최솟값을 구해주는 함수
    if(k == 1) v[k] = cost[k];
 
    if(v[k] != 0) return v[k];
 
    return v[k] = min(findMin(k-1), cost[k]);
}
 
 
ll f(int n){
    if(n == 1){
        return 0;
    }
    if(dp[n] != -1) return dp[n];
    return dp[n] = f(n-1) + dist[n-1]*findMin(n-1);
}
int main(){
    memset(dp, -1, sizeof(dp));
    int n; scanf("%d", &n);
    for(int i = 1; i < n; i++){
        scanf("%d", &dist[i]);
    }
    for(int i = 1; i <= n ;i++){
        scanf("%d", &cost[i]);
    }
    printf("%lld", f(n));
 
}