260409 TIL

//양궁대회 문제. 뭔 대회 규칙이 이런가 싶다마는...
//dfs를 활용해서 풀었고, 여러가지 규칙들을 세밀하게 적용하는 부분이 생각보다 많이 어려웠음
//그래도 잘 풀리긴 해서 다행
#include <string>
#include <vector>

using namespace std;

int maxdiff = 0;
vector<int> bestscore = {-1};

void DFS(int n, const vector<int>& info, vector<int> currentscore, int depth){
    if (depth == 11 || n == 0)
    {
        currentscore[10] += n;
        int lionscore = 0;
        int apeachscore = 0;
        
        for(int i = 0; i < 11; i++)
        {
            if (currentscore[i] == 0 && info[i] == 0) continue;
            if (currentscore[i] > info[i]) lionscore += 10 - i;
            else apeachscore += 10 - i;
        }
        
        int diff = lionscore - apeachscore;
        
        if (diff > 0 && diff > maxdiff)
        {
            maxdiff = diff;
            bestscore = currentscore;
        }
        else if (diff > 0 && diff == maxdiff)
        {
            for(int i = 10; i >= 0; i--)
            {
                if (currentscore[i] > bestscore[i])
                {
                    bestscore = currentscore;
                    break;
                }
                else if (currentscore[i] < bestscore[i]) break;
            }
        }
        
        return;
    }
    
    DFS(n, info, currentscore, depth + 1);
    
    if (n > info[depth])
    {
        int nextn = n - (info[depth] + 1);
        currentscore[depth] = info[depth] + 1;
        DFS(nextn, info, currentscore, depth + 1);
    }
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
    DFS(n, info, vector<int>(11, 0), 0);
    
    answer = bestscore;
    
    return answer;
}