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

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

12786번: INHA SUIT

1. 주의할 점

- 구멍이 있는 나무의 기준으로 왼쪽을 살펴보도록 한다

- 우선순위큐를 사용할 경우 추가적인 조건들이 필요한것 같다

 

2. 구현

- 첫 번째 시도: 우선순위 큐 사용 -> 초능력을 적게 쓴 경우가 Top으로 오도록하여 가장 오른쪽 나무에 다다르면 성공했다고 가정 (실패 -> 결국 우선순위 큐를 사용해서는 못품)

 

- 두 번째 시도: DP를 사용

  구멍이 뚫린 현재 나무를 기준으로 왼쪽을 살펴본다(O,A,B,C의 기능을 사용해서 현재로 올 수 있는지 + 올 수 있는 지    점에 구멍이 있는지)

  추가적인 조건으로는 왼쪽 나무의 모든 높이를 조사해서 구멍이 있다면 해당 나무에서 사용한 초능력 횟수 +1 만큼을    위에서 계산한값과 비교해서 가장 작은 값을 저장한다.

  마지막으로, DP가 모두 끝나고 가장 오른쪽에 있는 나무를 기준으로 모든 높이를 조사하면서 사용한 초능력의 횟수가    최대 사용가능 횟수보다 적거나 같을 경우 : 답 1, 아닌경우 : 답 -1

 

#define MAX 987654321
#include <iostream>
#include <algorithm>
using namespace std;
bool visit[101][21][51] = { false, };		//idx,구멍위치,사용한 제한횟수
bool tree[101][21] = { false, };
int dp[101][21];

int main() {
	int num, ability, hole, height;
	cin >> num >> ability;
	for (int i = 0; i < num; i++) {
		cin >> hole;
		for (int j = 0; j < hole; j++) {
			cin >> height;
			tree[i + 1][height] = true;
		}
	}
	for (int i = 0; i <= num; i++)
		for (int j = 1; j < 21; j++)
			dp[i][j] = MAX;
	tree[0][1] = true;
	dp[0][1] = 0;
	for (int j = 1; j <= num; j++) {
		for (int i = 1; i <= 20; i++) {
			if (tree[j][i]) {
				if (tree[j - 1][i])
					dp[j][i] = min(dp[j][i], dp[j - 1][i]);
				if (tree[j - 1][i - 1])
					dp[j][i] = min(dp[j][i], dp[j - 1][i - 1]);
				if (tree[j - 1][i + 1])
					dp[j][i] = min(dp[j][i], dp[j - 1][i + 1]);				
				if (i == 20) {
					for (int k = 10; k < 21; k++)
						if(tree[j-1][k])
							dp[j][i] = min(dp[j][i], dp[j - 1][k]);
				}
				if (i % 2 == 0 && tree[j - 1][i / 2])
					dp[j][i] = min(dp[j][i], dp[j - 1][i / 2]);
				for (int k = 1; k < 21; k++) {
					if (tree[j - 1][k])
						dp[j][i] = min(dp[j][i], dp[j - 1][k] + 1);
				}
			}
		}
	}
	int result = MAX;
	for (int i = 1; i < 21; i++) {
		if (dp[num][i] > ability) continue;
		result = min(result, dp[num][i]);
	}
	if (result == MAX) result = -1;
	cout << result;
	system("pause");
	return 0;
}