백준 14863번 서울에서 경산까지

🔒[문제 url]

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

🔑알고리즘

걸리는 시간을 물건의 무게, 모금액을 물건의 가치로 생각하여
knapsack을 적용해 해결한다.
dp[i][j]는 $j$의 시간을 소비하여 $i$번 구간을 지날 때의 최대 모금액이다.

• 한 도시를 지나갈 때, 고려해야할 case가 도보와 자전거 두 가지이므로,
  dp[i][j]를 갱신할 때 두 가지를 모두 고려해야한다.

🐾부분 코드

// Init
dp[1][walk[1].first] = walk[1].second;
dp[1][bike[1].first] = max(dp[1][bike[1].first],bike[1].second);

<dp 배열 초기화>
도보와 자전거의 소요 시간이 동일할 수 있으므로,
max(dp[1][bike[1].first],bike[1].second)로 초기화한다.

for(int i = 2; i <= n; i++)
    for(int j = 1; j <= k; j++)
        if(dp[i-1][j])
        {
            if(j + walk[i].first <= k)
                dp[i][j + walk[i].first] =
                        max(dp[i][j + walk[i].first], dp[i-1][j] + walk[i].second);
            if(j + bike[i].first <= k)
                dp[i][j + bike[i].first] =
                        max(dp[i][j + bike[i].first], dp[i - 1][j] + bike[i].second);
        }

<dp 배열 갱신>
소요 시간이 $k$를 넘지않는 수단에 한하여,
$i$번 구간을 지날 때의 최대 모금액으로 갱신한다.

int ans = 0;
for(int i = 1; i <= k; i++) ans = max(ans,dp[n][i]);
cout << ans;

<답안 출력>
$n$개의 구간을 모두 지나온 경우 중, 최대 모금액을 출력한다.

🪄전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int,int> pii;
int n,k;
vector<pii> walk(101),bike(101);
int dp[101][100001];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        int a,b,c,d; cin >> a >> b >> c >> d;
        walk[i] = {a,b}; bike[i] = {c,d};
    }
}


void SOLVE()
{
    // Init
    dp[1][walk[1].first] = walk[1].second;
    dp[1][bike[1].first] = max(dp[1][bike[1].first],bike[1].second);

    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= k; j++)
            if(dp[i-1][j])
            {
                if(j + walk[i].first <= k)
                    dp[i][j + walk[i].first] =
                            max(dp[i][j + walk[i].first], dp[i-1][j] + walk[i].second);
                if(j + bike[i].first <= k)
                    dp[i][j + bike[i].first] =
                            max(dp[i][j + bike[i].first], dp[i - 1][j] + bike[i].second);
            }

    int ans = 0;
    for(int i = 1; i <= k; i++) ans = max(ans,dp[n][i]);
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

초기화와 답안 출력에서 꽤 오래 헤맨 문제였다.
$n$개의 구간을 모두 거친 경우에서만 답안을 고려해야한다는 것을 놓치고
for문을 돌때마다 ans를 갱신한 것,
도보와 자전거의 소요 시간이 동일할 경우를 대비해 max를 이용하여 초기화해야함을 놓친 것..!
디테일한 경우의 수를 빠르게 빠르게 캐치하는 것이 아직은 어렵다..
앞으로도 어려울 것같다..😅