Bin_S+StudyRoom

• 문제

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

1. 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
2. 두 번째로 공격받는 SCV는 체력 3을 잃는다.
3. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

• 출력

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

• 예제 입력

3
12 10 4

3
54 18 6

1
60

3
1 1 1

2
60 40

• 예제 출력

2

6

7

1

9

• 접근방식

그래프로 표현하였을때 3개의 scv가 0,0,0이 되는 최소 레벨을 구하면 된다. > bfs로 해결 가능

단, scv의 체력이 0 이하가 되었을때는 음수로 되지 않게 예외처리 필요

• 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int n, scv[3], visited[64][64][64];

int _a[6][3] =
{
	{9, 3, 1},
	{9, 1, 3},
	{3, 1, 9},
	{3, 9, 1},
	{1, 3, 9},
	{1, 9, 3}
};

struct A
{
	int a, b, c;
};

queue<A> q;

int bfs(int a, int b, int c)
{
	visited[a][b][c] = 1;
	q.push({ a,b,c });
	while (q.size())
	{
		int a = q.front().a;
		int b = q.front().b;
		int c = q.front().c;
		q.pop();

		if (visited[0][0][0])	break;
		for (int i = 0; i < 6; i++)
		{
			// 음수 방지
			int na = max(0, a - _a[i][0]);
			int nb = max(0, b - _a[i][1]);
			int nc = max(0, c - _a[i][2]);

			if (visited[na][nb][nc])	continue;
			visited[na][nb][nc] = visited[a][b][c] + 1;
			q.push({ na,nb,nc });
		}
	}
	return visited[0][0][0] - 1;
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> scv[i];
	}
	cout << bfs(scv[0], scv[1], scv[2]);
	return 0;
}

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