코드 복사/붙여넣기 하는 당신이 아름답습니다.

12869 : 뮤탈리스크

풀이

음 원래 dp로 풀려고 했는데 그냥 bfs로 풀었다.

dp[i][j][k] = 1번, 2번, 3번 scv의 체력으로 두고 풀어도 된다.

코드

#include <bits/stdc++.h>
using namespace std;

int N, A[3], ans = 987654321;
const int D[6][3] = { {1,3,9},{1,9,3},{3,1,9},{3,9,1},{9,1,3},{9,3,1} };
bool chk[61][61][61][20];

struct ABC { 
	int a, b, c, x;
	ABC() {}
	ABC(int a, int b, int c, int x) : a(a), b(b), c(c), x(x) {}
};

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
	
	queue<ABC> q;
	q.push(ABC(A[0], A[1], A[2], 0));
	chk[A[0]][A[1]][A[2]][0] = 1;
	while (!q.empty()) {
		ABC now = q.front();
		q.pop();
		if (!now.a && !now.b && !now.c) ans = min(ans, now.x);
		for (int i = 0; i < 6; ++i) {
			int a = now.a - D[i][0], b = now.b - D[i][1], c = now.c - D[i][2], x = now.x + 1;
			if (a < 0) a = 0; if (b < 0) b = 0; if (c < 0) c = 0;
			if (!chk[a][b][c][x]) {
				chk[a][b][c][x] = 1;
				q.push(ABC(a, b, c, x));
			}
		}
	}
	printf("%d", ans);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-08 11:38

Read more posts by this author