어흥
[백준 12786] INHA SUIT (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/12786
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