[프로그래머스/C++] 양궁대회

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 처음 봤을 때 어떤 것을 기준으로 탐색을 해야할지 고민을 했다.

 

만약 특정 점수에 a개의 화살을 맞추는 경우의 수를 구했다면 a!과 같은 형태의 시간복잡도가 나오게 된다.

 

하지만 반대로 각 점수판에서 특정 캐릭터가 이기는 경우의 수로 계산을 하면 [이긴다, 진다] 두 경우로 나오기 때문에 2^n의 시간 복잡도로 빠르게 문제를 해결 할 수 있게 된다.

 

그러므로 10개의 점수에 대해 라이언이 이기는 경우를 모두 탐색하고, 만약에 라이언이 이 경우대로 이기는게 가능하다면, 점수 차이를 비교했다.

 

+ 여기서 라이언이 쏠 화살이 남는 경우가 생길 수 있다.

 

문제에서 같은 점수차이일 때 낮은 점수에 화살을 많이 쏜 경우를 return하라는 조건이 있었으므로 남는 화살은 전부 0점에 쏘면 모든 경우를 구할 수 있다.

 

 

 

​

[아이디어 정리]

1. 모든 경우를 탐색할 때, 특정 점수에 대해 라이언이 이기는 경우 지는 경우로 나누어 탐색한다.
2. return 하는 조건에 따라 남는 화살은 전부 0점에 쏜다.
3. 점수 차가 가장 많이 나는 경우를 return 한다.

 

 

 

Code

 

 

#include <string>
#include <vector>

using namespace std;

int maxScore=0;
vector<int> retAns(11,0);
vector<bool> WinLose;
void CalcNowCase(vector<int> &info, int n, int pScore)
{
    vector<int> nowT(11,0);
    int lScore=0;
    for (int i=0; i<11; i++)
    {
        if (WinLose[i])
        {
            nowT[i]=info[i]+1;
            n-=nowT[i];
            lScore+=10-i;
            if (n<0){
                return;
            }
            if (info[i]>0)
            {
                pScore-=10-i;
            }
        }
    }
    if (n>0)
    {
        nowT[10]+=n;
    }
    int ccc=lScore-pScore;
    if (maxScore<ccc)
    {
        maxScore=ccc;
        retAns=nowT;
    }
    else if (maxScore==ccc)
    {
        for (int i=10; i>=0; i--)
        {
            if (retAns[i]>nowT[i])
            {
                break;
            }
            else if (retAns[i]<nowT[i])
            {
                retAns=nowT;
                break;
            }
        }
    }
}

void makeCase(int deg, vector<int> &info, int n,int pScore)
{
    if (deg>=10)
    {
        CalcNowCase(info,n,pScore);
        return;
    }
    WinLose[deg]=true; //이기는 경우
    makeCase(deg+1,info,n,pScore);
    WinLose[deg]=false; // 비기거나 지는 경우
    makeCase(deg+1,info,n,pScore);
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
    int pScore=0;
    for (int i=0; i<11; i++){
        if (info[i]>0){
            pScore+=10-i;
        }
    }
    WinLose=vector<bool> (11,false); //라이언이 이기는 경우
    makeCase(0,info,n,pScore);
    if (maxScore==0){
        return vector<int> (1,-1);
    }
    return retAns;
}

 

---

이번에도 느꼈지만, LV2 문제들이 은근히 어려운 문제들이 있는 것 같다.

이 문제는 그 중에서도 탐색 기준을 어떻게 잡아서 시간을 줄일지에 대한 문제였다.

문제를 잘 풀기 위해 다양한 방법으로 생각하는 능력을 더 길러보자...

 

프로그래머스