어흥

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

알고리즘/백준

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

라이언납시오 2020. 3. 10. 23:12
728x90
반응형

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

 

12786번: INHA SUIT

평소 Iron man을 좋아하던 규환이는 Iron man Suit에 영감을 받아 Inha Suit를 만들게 되었다. 규환이는 Suit를 입고 모든 나무의 높이가 20m인 숲을 지나서 인하대로 놀러가려고 한다. 하지만 Inha Suit는 Iron man Suit와 다르게 위아래로만 움직일 수 있다는 큰 결점을 갖고 있었고 그마저도 최대 20m까지 올라갈 수 있었다.  이동 기능은 가만히 있는 O기능, 위로 1m 이동하는 A기능, 현재 높이만큼 위로 이동하는

www.acmicpc.net

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;
}
728x90
반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준 15989] 1,2,3 더하기 4 (C++)  (0) 2020.03.11
[백준 1072] 게임 (C++)  (0) 2020.03.11
[백준 14499] 주사위 굴리기 (C++)  (0) 2020.03.10
[백준 3020] 개똥벌레 (C++)  (0) 2020.03.10
[백준 3079] 입국심사 (C++)  (0) 2020.03.10
Comments