양궁대회 92342

문제

접근 방법

DFS로 푸는 게 좋다고 생각했다.
모든 경우의 수를 따져도 오천 개가 안 된다고 생각했다. 그렇기에 DFS를 돌며 점수 차를 확인하면 가장 큰 점수 차일 경우 갱신하고 점수 차가 같으면 더 낮은 점수를 많이 맞춘 것을 갱신하는 방법으로 접근하면 된다고 생각했다.

코드

#include <vector>
using namespace std;
int maxNum = 0;
vector<int> maxArr;
bool isLess(vector<int> &cur)
{
    if (maxArr.empty())
        return true;
    for (int i = 10; i >= 0; --i)
    {
        if (cur[i] > maxArr[i])
            return true;
        else if (cur[i] < maxArr[i])
        {
            return false;
        }
    }
    return false;
}

void dfs(vector<int> &info, vector<int> &cur, int idx, int chance, int mySum, int enemySum)
{
    if (idx == 11)
    {
        cur[idx - 1] = chance;
        int sumGap = mySum - enemySum;
        if (sumGap >= maxNum)
        {
            if (sumGap == maxNum && isLess(cur) || sumGap > maxNum)
                maxArr = vector<int>(cur);
            maxNum = sumGap;
        }
        return;
    }
    if (info[idx] < chance)
    {
        cur[idx] = info[idx] + 1;
        dfs(info, cur, idx + 1, chance - (info[idx] + 1), mySum + (10 - idx), (info[idx] ? enemySum - (10 - idx) : enemySum));
        cur[idx] = 0;
    }
    dfs(info, cur, idx + 1, chance, mySum, enemySum);
}

vector<int> solution(int n, vector<int> info)
{
    int enemySum = 0;
    for (int i = 0; i < 10; i++)
    {
        if (info[i])
            enemySum += 10 - i;
    }
    vector<int> answer(11);
    dfs(info, answer, 0, n, 0, enemySum);
    if (maxNum == 0)
        return vector<int>(1, -1);
    return maxArr;
}

풀이

처음 제출에서 3개의 테스트 케이스가 틀렸었다. 한 개는 비기는 경우가 있을 수 있기에 maxNum을 0으로 초기화했어야 하는 경우였고 나머지 2개는 가장 작은 것을 더 많이 맞춘 경우였다.
가장 작은 것을 더 많이 맞춘 경우는 잘못 이해해서 틀렸다.