[C++] 백준 17484 진우의 달 여행 (Small)

 
#include <iostream>
#include <string>
#include <vector>
 
int N = 0;
int K = 0;
int vec[10][10] = {};
int vecAns[10][10][4] = {};
 
int DFS(int iX, int iY, int iDir)
{
    if (iX == N)
        return 0;
 
    if (!vecAns[iX][iY][iDir])
        return vecAns[iX][iY][iDir];
 
    if (iDir != 1 && iY - 1 >= 0)
        vecAns[iX][iY][iDir] = std::min(vecAns[iX][iY][iDir], DFS(iX + 1, iY - 1, 1) + vec[iX][iY]);
 
    if (iDir != 2)
        vecAns[iX][iY][iDir] = std::min(vecAns[iX][iY][iDir], DFS(iX + 1, iY, 2) + vec[iX][iY]);
 
    if (iDir != 3 && iY + 1 < K)
        vecAns[iX][iY][iDir] = std::min(vecAns[iX][iY][iDir], DFS(iX + 1, iY + 1, 3) + vec[iX][iY]);
 
    return vecAns[iX][iY][iDir];
}
 
int main()
{
    std::cin >> N >> K;
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < K; ++j)
        {
            std::cin >> vec[i][j];
 
            for (int z = 0; z < 4; ++z)
            {
                vecAns[i][j][z] = 1000000;
            }
        }
    }
 
    int iAns = 1000000;
    for (int i = 0; i < K; ++i)
    {
        iAns = std::min(iAns, DFS(0, i, 0));
    }
 
    std::cout << iAns;
 
    return 0;
}
 

DP를 써야할 것 같은데 DP보다는 DFS로 해야했다.

처음에 DP로 저장하고 min인 것들로만 구해서 계산했더니 min인 것들의 집합이 계산되어서 문제가 되더라...