[Algorithm] Programmers :: 양궁대회

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

vector<int> curRoute = { 0,0,0,0,0,0,0,0,0,0,0 };
vector<int> answerRoute;
int maxScoreGap = -1;
 
int Check(vector<int>& info)
{
    int aSum = 0;
    int lSum = 0;
 
    for (int i = 0; i < 10; ++i) 
    {
        if (curRoute[i] == 0 && info[i] == 0) continue;
        if (curRoute[i] > info[i]) lSum += 10 - i;
        else aSum += 10 - i;
    }
 
    if (lSum > aSum) return lSum - aSum;
    else return 0;
}
 
void DFS(int n, int index, vector<int>& info)
{
    if (n == 0) // 다 쏘면
    {
        int check = Check(info); // 어피치보다 점수높은지 체크.
 
        if (check)
        {
            if (check > maxScoreGap)
            {
                maxScoreGap = check;
                answerRoute = curRoute;
            }
        }
 
        return;
    }
 
    for (int i = index - 1; i >= 0; --i)
    {
        if (n >= info[i] + 1)
        {
            curRoute[i] = info[i] + 1;
            DFS(n - (info[i] + 1), i, info);
            curRoute[i] = 0;
        }
    }
}
 
vector<int> solution(int n, vector<int> info)
{
    vector<int> answer = { -1 };
 
    for (int i = 10; i >= 0; --i) // 점수 낮은것부터 갱신.(조건에 만족하기위해서)
    {
        if (i == 10) // 0점짜리면
        {
            for (int j = 0; j <= n - 1; ++j) // 0점짜리에 n-1발까지 쏴보
            {
                curRoute[i] = j;
                DFS(n - j, i, info);
                curRoute[i] = 0;
            }
        }
        else if (n >= info[i] + 1)
        {
            curRoute[i] = info[i] + 1;
            DFS(n - (info[i] + 1), i, info);
            curRoute[i] = 0;
        }
 
    }
 
    if (answerRoute.size() > 0) return answerRoute;
    else return { -1 };
}

그리디문젠가? 하다가 여러가지 경우의수를 검사해야한다는걸 깨닫고 DFS로 완전탐색을 수행했다.

여기서 중요한건, '최대 점수차'를 구함과 동시에 루트가 두개이상일 경우, 최대한  '낮은 점수'의 과녁을 맞춘 경로를 리턴해야한다는 것이였다.

 

그래서 아예 낮은과녁부터 맞추면서 수행했는데 여기서 또 명심해야할 것은, n발을 전부 쏴야한다는 것.

즉 이미 '최대 점수차'를 구했는데 화살이 남는 경우가 있다. 이럴경우에는 남는 화살을 전부 0점짜리에 쏴버려야 한다.

그래서 아예 0점짜리를 0발부터 n-1발까지 전부 쏘는 경우도 추가했다.

1점이라도 더 높긴해야하니까 n발을 쏘면 안되고 n-1발까지만 쏴야한다.