[ SWEA 9092 ] 마라톤 (C++)

SWExpertAcademy의 마라톤(9095 / D5) 문제이다.

[ 문제풀이 ]

K개의 체크포인트를 건너 뛰면서 달려야 하는 최소 거리를 구해야 하는 문제이다.

먼저, 모든 체크포인트에 대해서 건너뛰는 경우와 뛰지 않는 경우를 완전탐색을 진행할 경우, 하나의 체크포인트 당 건너 뛰는 경우와 건너뛰지 않는 경우 2가지 선택권이 있고, 체크포인트의 최대값은 약 500이니, 어마어마한 경우의 발생하게 된다.

따라서, 본인은 DFS 와 메모이제이션을 이용해서 접근하였다.

메모이제이션을 본인은 2차원 배열 int DP[][]를 통해서 표현해 주었다.

DP[A][B] = C 의 의미는, "현재 A번 체크포인트이고 , 건너뛸 수 있는 횟수가 B번 남았을 때 달려야 하는 최소거리는 C입니다." 를 의미한다.

탐색을 할 때, 고려해야 할 부분은 2가지가 있다.

1. 건너 뛰었을 때, 도착점을 지나쳐 버리는지

2. 건너 뛰려는 횟수가, 건너 뛰려는 칸 보다 더 많은지

위와 같이 2가지를 고려해 주면 된다.

만약, 현재 칸에서 x개의 체크포인트를 건너뛰었는데, 도착점을 넘어가버린다면 안된다.

또한, 현재 건너 뛸 수 있는 체크포인트가 1개 남았는데, 이 상태에서 2개의 체크포인트를 한번에 건너 뛰는 것도 불가능 하다.

위의 2가지 조건을 고려하면서 탐색을 진행해 주었다. 그 과정에서 DP값의 최소값을 갱신하면서 답을 도출해 주었다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <cmath>
#define endl "\n"
#define MAX 510
using namespace std;
 
struct COORD
{
    int x;
    int y;
};
 
int N, K, Answer;
COORD Coord[MAX];
int DP[MAX][MAX];
 
int Min(int A, int B) { return A < B ? A : B; }
 
void Initialize()
{
    memset(DP, -1, sizeof(DP));
}
 
int Dist(int Pos1, int Pos2)
{
    return abs(Coord[Pos1].x - Coord[Pos2].x) + abs(Coord[Pos1].y - Coord[Pos2].y);
}
 
void Input()
{
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        cin >> Coord[i].x >> Coord[i].y;
    }
}
 
int DFS(int Cur, int Spare_Jump)
{
    if (Cur == N - 1) return 0;
    if (DP[Cur][Spare_Jump] != -1) return DP[Cur][Spare_Jump];
    
    DP[Cur][Spare_Jump] = 2e9;
    for (int i = 0; i <= K; i++)
    {
        int Next = Cur + i + 1;
        if (Next >= N) continue;
        if (Spare_Jump - i < 0) continue;
 
        DP[Cur][Spare_Jump] = Min(DP[Cur][Spare_Jump], DFS(Next, Spare_Jump - i) + Dist(Cur, Next));
    }
    return DP[Cur][Spare_Jump];
}
 
void Solution()
{
    Answer = DFS(0, K);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}