12869 - 뮤탈리스크

문제 풀이

처음에 문제를 보고 가장 체력이 많이 남은 scv에 가장 센 공격을 수행하는 그리디한 방법으로 코드를 짜봤지만 틀렸다.
예제코드 2,3,4,5는 맞지만 예제코드 1번에서 그리디한 방법으로 풀면 안된다는 것을 알려줬는데 확인하지 못하고 그리디로 접근해버렸다 -> 예제로 주어진 입력은 분석잘하기!
N의 최대가 3이므로 모든 경우를 탐색하는게 맞는거 같아서 dp를 이용하여 모든 경우를 탐색하였다.

---

그리디로 접근한 첫번째 풀이

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int attack[3] = { 9,3,1 };
vector<int> v;
stack<int> s;
int ans;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }
    while (v.size()) {
        ans++;
        sort(v.begin(), v.end(), greater<>());
        for (int i = 0; i < v.size(); i++) {
            if (i == 0) {
                v[i] = v[i] - 9;
            }
            else if (i == 1) {
                v[i] = v[i] - 3;
            }
            else {
                v[i] = v[i] - 1;
            }
            if (v[i] <= 0) { s.push(i); }
        }
        while (!s.empty()) {
            int x = s.top();
            s.pop();
            v.erase(v.begin() + x);
        }
    }
    cout << ans;
}

---

dp로 완전탐색 정답 풀이

#include <iostream>
#include <cstring>
using namespace std;

int hp[3];
int scv[61][61][61];
int N;

void mutalisk(int scv1, int scv2, int scv3, int cnt) {
    if (scv[scv1][scv2][scv3] <= cnt) { return; } // scv가 작을때 이미 더 효과적인 방법을 dp에서 저장하고 있음
                                                  // scv가 cnt랑 같을 때 이미 같은 방법을 전에 수행함
                                                  // 그러므로 두가지 경우에 대해선 더이상 계산 할 필요가 없음
    scv[scv1][scv2][scv3] = cnt; // dp테이블에 cnt저장

    if (scv1 == 0 && scv2 == 0 && scv3 == 0) { return; }// 답이 나오면 종료



    // 공격의 모든 경우 탐색
    mutalisk(max(scv1 - 9,0), max(scv2 - 3, 0), max(scv3 - 1, 0), cnt + 1);
    mutalisk(max(scv1 - 9, 0), max(scv2 - 1, 0), max(scv3 - 3, 0), cnt + 1);
    mutalisk(max(scv1 - 3, 0), max(scv2 - 9, 0), max(scv3 - 1, 0), cnt + 1);
    mutalisk(max(scv1 - 3, 0), max(scv2 - 1, 0), max(scv3 - 9, 0), cnt + 1);
    mutalisk(max(scv1 - 1, 0), max(scv2 - 3, 0), max(scv3 - 9, 0), cnt + 1);
    mutalisk(max(scv1 - 1, 0), max(scv2 - 9,0), max(scv3 - 3, 0), cnt + 1);

}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> hp[i];
    }
    memset(scv, 999999, sizeof(scv));
    mutalisk(hp[0], hp[1], hp[2], 0);
    cout << scv[0][0][0] << '\n';
}

얻은 점

1. dp문제 숙달
2. 코드부터 치려하지말고 예제의 입력 분석 제대로 하기