코딩 테스트 공부 118668

문제

접근 방법

150^2*100은 2250000이다.
큰 숫자긴 하지만 모두 확인할 수 있다.

현재 가지고 있는 알고력과 코딩력에서 시작한 뒤 도착 지점으로 가면 반환하는 식으로 해결하면 된다. (그 뒤의 값은 확인할 필요가 없다)

시작 지점보다 낮은 값은 확인할 필요가 없다. (시작 지점이 이미 지나간 지점은 필요가 없다는 뜻이다)

코드

#include <string>
#include <vector>
using namespace std;
int min(int num1, int num2)
{
    return num1 > num2 ? num2 : num1;
}
int max(int num1, int num2)
{
    return num1 < num2 ? num2 : num1;
}
int solution(int alp, int cop, vector<vector<int>> problems)
{
    vector<vector<int>> dp(151, vector<int>(151, 301));
    int maxA = alp, maxC = cop;
    problems.push_back({0, 0, 1, 0, 1});
    problems.push_back({0, 0, 0, 1, 1});
    for (vector<int> problem : problems)
    {
        maxA = max(maxA, problem[0]);
        maxC = max(maxC, problem[1]);
    }
    dp[alp][cop] = 0;
    for (int i = alp; i <= 150; ++i)
        for (int j = cop; j <= 150; ++j)
        {
            if (i == maxA && j == maxC) // 도착했다면
                return dp[i][j];
            for (vector<int> problem : problems)
            {
                int reqA = problem[0], reqC = problem[1], getA = problem[2], getC = problem[3], time = problem[4];
                if (reqA > i || reqC > j) // 요구 사항을 못 넘는다면
                    continue;
                int k = min(i + getA, maxA), l = min(j + getC, maxC);
                dp[k][l] = min(dp[k][l],  dp[i][j] + time);
            }
        }
}

풀이

여러 경우를 생각 안 하고 풀면 꼬이기 쉬운 문제인 것 같다.

문제를 기준으로 반복문을 돌았더니 반례는 맞춰도 제출하면 틀리게 됐다.
아마도 먼저 사용된 문제가 저장된 값을 휘저어 놓은 것 같다.

다른 사람의 풀이를 찾아보니 알고력과 코딩력을 기준으로 반복문을 돌고 그 뒤에 문제를 확인하는 것이다.
그 방법을 통하면 현재 알고력과 코딩력을 기준으로 DP 값을 갱신하기 쉽기에 좋은 방법인 것 같다. (다시 생각해 보면 DP의 기준이 되는 값으로 반복문을 사용하는 게 맞는 방법이었다)

이미 한쪽이 완료된 경우를 해결하기 위해선 가장 큰 값을 확인할 때 초기의 알고력과 코딩력으로 채워주는 것이 좋다.
문제를 풀어서 얻는 값이 최종적으로 모든 문제를 풀 수 있는 값을 지날 수 있기에 DP를 갱신할 때 둘 중 낮은 값으로 갱신해 주는 방법을 사용해 주면 좋다. (그렇게 하면 평소에는 풀어서 얻는 값이 낮기에 풀어서 얻는 값을 기준으로 DP가 갱신되고 모든 문제를 풀 수 있는 값을 지날 때는 모든 문제를 풀 수 있는 값으로 갱신이 되기 때문이다)

굉장히 실수하기 좋은 문제인 것 같다.