[백준 12786번] INHA SUIT (C++)

문제링크 : https://www.acmicpc.net/problem/12786

12786번: INHA SUIT

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

bool hole[101][21];
int dp[101][21];

int main() {
	int N, T, M, H, result = MAX;
	cin >> N >> T;
	for (int i = 0; i < N; i++) 
	{
		cin >> M;
		for (int j = 0; j < M; j++) 
		{
			cin >> H;
			hole[i + 1][H] = true;
		}
	}

	fill(&dp[0][0], &dp[N+1][21], MAX);

	hole[0][1] = true;
	dp[0][1] = 0; //출발점

	for (int i = 0; i < N; i++) 
	{
		for (int j = 1; j <= 20; j++) 
		{
			if(!hole[i][j]) continue;
			if (hole[i+1][j]) dp[i+1][j] = min(dp[i+1][j], dp[i][j]); //O버튼
			if (hole[i+1][j+1]) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]); //A버튼
			if (hole[i+1][j-1]) dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j]); //C버튼
			if (hole[i+1][min(20, j*2)]) dp[i+1][min(20, j*2)] = min(dp[i+1][min(20, j*2)], dp[i][j]); //B버튼
			for (int k = 1; k <= 20; k++)
			{
				if (hole[i+1][k]) dp[i+1][k] = min(dp[i][j] + 1, dp[i+1][k]); //T버튼 (텔레포트 할때만 +1)
			}
		}
	}

	for (int i = 1; i <= 20; i++) 
	{
		if (dp[N][i] > T) continue;
		result = min(result, dp[N][i]);
	}
	cout << (result == MAX ? -1 : result);
	return 0;
}

 

다익스트라 또는 DP로 푸는 문제이다.

나는 DP를 이용하여 풀었다.

 

만약 현재 위치에 구멍이 있다면, 다음 갈 수 있는 곳에 구멍이 있는 지 확인한다.

다음 구멍으로 갈 수 있는 경우는 다음과 같다.

 

O버튼 : 오른쪽으로 이동 -> hole[i+1][j] 체크
A버튼 : 오른쪽 + 위로 이동 -> hole[i+1][j+1] 체크
C버튼 : 오른쪽 + 아래로 이동 -> hole[i+1][j-1] 체크
B버튼 : 오른쪽 + 2배로 이동 (최대치 20) -> hole[i+1][min(20, j*2)] 체크
T버튼 : 무조건 오른쪽 이동 -> hole[i+1][k] 체크 (이 경우는 카운트해야하므로 이때만 + 1를 한다)

 

각 경우에 대해서 dp를 갱신하고 O, A, C, B 버튼의 경우는 그 전의 dp 값을 가져오고 T버튼의 경우만 그 전의 dp에 1을 더하여 갱신한다.

 

이후 T 횟수가 정해진 횟수를 초과하는지를 체크하고 이에 따라서 -1인지, T 이하의 횟수인지를 출력하면 된다.