[Programmers] 양궁대회(Lv.2)

풀이 소요시간 : 60분 초과(실패)

DFS, 백트래킹으로 풀이 접근은 성공했지만 유형 안에서 정석 풀이 방식을 떠올리지 못했다.

정석 접근의 핵심

1. 높은 점수부터 어피치의 점수 + 1 을 할당한다.
2. 화살 갯수가 모자란다면 해당 점수는 포기하고 다음 점수로 넘어간다.
3. 마지막 남은 화살은 가장 낮은 0점에 몰아준다.

순서대로 접근하여 풀이가 가능한 문제였다. 필자는 0점부터 10점까지 화살 갯수를 모두 고려한 완전탐색을 구현하였고, 10초의 제한시간임에도 불구하고 시간초과로 통과하지 못했다. 레벨 2의 문제도 제대로 해결하지 못하여 주눅들었지만, 항상 모르는 것이 나오면 다행이라는 마음가짐으로 공부해야한다.

전체 코드

#include <string>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int N;
vector<int> Ans(11);
vector<int> Ryan(11);
vector<int> Apeach(11);
int MAX_DIFF = 0;


bool Same_Value() {
    for(int i = 10; i >= 0; i--)
    {
        //새롭게 갱신
        if(Ans[i] < Ryan[i])
        {
            return true;
        }
        else if(Ans[i] > Ryan[i])
        {
            return false;
        }
    }
}

void Check() {
    
    int Ryan_Total = 0;
    int Apeach_Total = 0;
    
    for(int i = 0; i <= 10; i++)
    {
        if(Apeach[i] < Ryan[i]) Ryan_Total += (10 - i);
        else if(Apeach[i] > 0) Apeach_Total += (10 - i);
    }
    
    if(Ryan_Total - Apeach_Total > 0)
    {
        //최대 값 갱신
        if(MAX_DIFF < Ryan_Total - Apeach_Total)
        {
            MAX_DIFF = Ryan_Total - Apeach_Total;
            Ans = Ryan;
        }
        else if(MAX_DIFF == Ryan_Total - Apeach_Total)
        {
            if(Same_Value() == true)
            {
                Ans = Ryan;
            }
        }
    }
    
}

void Dfs(int Count, int Arrow) {
    
    if(Count == 11 || Arrow == 0)
    {
        Ryan[10] = Arrow;
        Check();
        Ryan[10] = 0;
        return;
    }
    
    if(Arrow > Apeach[Count])
    {
        Ryan[Count] = Apeach[Count] + 1;
        Dfs(Count + 1, Arrow - (Apeach[Count] + 1));
        Ryan[Count] = 0;
    }
    
    Dfs(Count + 1, Arrow);
    
}


vector<int> solution(int n, vector<int> info) {
    
    N = n;
    for(int i = 0; i <= 10; i++)
    {
        Apeach[i] = info[i];
    }
    //전역변수 세팅
    
    Dfs(0, N);
    //백 트래킹 -> 모든 경우의 수 고려
    
    if(MAX_DIFF == 0)
    {
        return {-1};
    }
    else
    {
        return Ans;
    }
    
}