[1일 1알고] G4 27114 조교의 맹연습

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

 

A, B, C값을 조합해 정확하게 K가 되는 최솟값을 출력해야 하므로 일단 knapsack 문제와 비슷할 것이라는 느낌이 있었습니다.

A,B,C,K가 최대 백만이기 때문에 충분할 것으로 생각하고 진행했습니다.

 

A,B,C는 중복사용이 가능하기 때문에 앞에서 부터 순차적으로 탐색했습니다.

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int MAX = 1000001;

    int A, B, C, K;
    cin >> A >> B >> C >> K;
    vector<vector<int>> dp(K + 1, vector<int>(4, MAX));

    dp[0][0] = 0;
    
    for (int i = 0; i <= K; ++i)
    {
        for (int dir = 0; dir < 4; ++dir)
        {
            int left_dir = (dir + 4 - 1) % 4;
            int right_dir = (dir + 1) % 4;
            int back_dir = (dir + 2) % 4;
            if (i - A >= 0 && dp[i - A][left_dir] != MAX)
            {
                dp[i][dir] = min(dp[i][dir], dp[i - A][left_dir] + 1);
            }
            if (i - B >= 0 && dp[i - B][right_dir] != MAX)
            {
                dp[i][dir] = min(dp[i][dir], dp[i - B][right_dir] + 1);
            }
            if (i - C >= 0 && dp[i - C][back_dir] != MAX)
            {
                dp[i][dir] = min(dp[i][dir], dp[i - C][back_dir] + 1);
            }
        }
    }

    if (dp[K][0] == MAX)
    {
        cout << -1;
    }
    else
    {
        cout << dp[K][0];
    }

    return 0;
}

방향을 2차원으로 펼치면 쉽게 해결할 수 있는 문제입니다.