조합을 이용한 풀이

안녕하세요 건학님 ㅎㅎ

이부분은 만약 SCV가 2개일 때 { 1, 3 }, {1, 3} ... 이런식으로 순열이 올바르게 뽑히지 않고 -> 1과 3으로만 구성되니 답이 안나오는 것 같습니다.

반면 {-9, -3, -1}의 경우 제대로 안뽑혀도 {-9, -3} 이 먼저 나오기 때문에 이를 통해 최대값으로 공격해서 답이 나온거구요.

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

int n, a[64][64][64], visited[64][64][64], hp[3];
int de[3] = {1, 3, 9};
vector<int> v;
vector<vector<int>> d;
struct A
{
    int a, b, c;
};
queue<A> q;

void make_list()
{
    do
    {
        for (int i : de)
        {
            v.push_back(i);
        }
        d.push_back(v);
        v.clear();
    } while (next_permutation(de, de + 3));
}

int bfs(int x, int y, int z)
{
    visited[x][y][z] = 1;
    q.push({x, y, z});
    while (q.size())
    {
        int x = q.front().a;
        int y = q.front().b;
        int z = q.front().c;
        q.pop();
        if (visited[0][0][0])
            break;
        for (vector<int> iv : d)
        {
            int nx = max(0, x - iv[0]);
            int ny = max(0, y - iv[1]);
            int nz = max(0, z - iv[2]);
            if (visited[nx][ny][nz])
                continue;
            visited[nx][ny][nz] = visited[x][y][z] + 1;
            q.push({nx, ny, nz});
        }
    }
    return visited[0][0][0] - 1;
}

int main()
{
    cin >> n;
    for (int i = 0; i < 3; i++)
    {
        cin >> hp[i];
    }
    make_list();
    cout << bfs(hp[0], hp[1], hp[2]);
}

이렇게 고쳐보시겠어요?

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변