[ 프로그래머스 양궁대회 (Lv2) ] (C++)

프로그래머스의 양궁대회(Lv2)문제이다.

 

[ 문제풀이 ]

어피치가 모두 화살을 쏜 후에, 라이언이 화살을 쐈을 때 화살을 어떻게 쏴야 라이언이 이길 수 있는지 구해야 하는 문제이다. 문제에서 제시한 조건들을 토대로 라이언이 어떻게 화살을 쏴야 이길 수 있는지부터 이야기해보고 이를 토대로 정답을 도출하는 과정에 대해서 순차적으로 진행해보자.

 

#1. 점수를 얻을 수 있는 방법

먼저 이 양궁대회에는 다음과 같은 조건이 존재한다.

"k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져 가는 것이 아니고 딱 k점만 가져가게 된다".

k점 과녁에 화살을 1개를 맞추든, 10개를 맞추든 똑같이 k점만 가져가게 된다는 것이다. 물론, 어피치와 라이언의 화살 관계에 대한 조건을 빼놓고 이야기하면 위와 같다는 것이다.

우리는 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법을 구해야 한다. 즉, 가장 큰 점수 차이로 우승을 하기 위해서는 어떻게 보면 "쓸데 없는 곳에 화살을 소모하면 안된다" 라는 것을 의미한다.

똑같은 k점에만 계속해서 화살을 쏘는 것은 특정 경우에는 필요할 수도 있겠지만, 그런 경우가 아니라면 굉장히 쓸모 없는 화살이 될 것이다.

 

두 번째로 k점을 얻기 위해서 라이언은 어피치보다 많은 화살을 쏴야한다.

어피치가 k점 과녁에 a개의 화살을 발사했다면, 라이언은 k점 과녁에 a개보다는 더 많은 화살을 쏴야지만 k점을 얻을 수 있는 것이다. 그럼 이 조건에서 "쓸데 없는 곳에 화살을 소모하는 경우"는 어떤 경우들이 있을까 ?? 아마 다음과 같은 경우들이 존재할 것이다.

1. k점 과녁에 a개 이하의 화살을 쏘는 경우

2. k점 과녁에 a개 보다 훨씬 더 많은 화살을 쏘는 경우

이 2가지 경우가 아마 쓸데 없는 곳에 화살을 소모하는 경우가 될 것이다.

왜 그런지에 대해서 이야기를 해보자.

먼저, k점 과녁에 a개 이하의 화살을 쏘게 되면 어떤 일이 일어나게될까 ? 라이언은 해당 k점을 얻지 못하고 어피치가 k점을 획득하게 될 것이다. 아예 k점 과녁에 화살을 안쏴버리면 화살이라도 아낄 수 있는데 a개 이하의 화살을 쏴버린다는 것은 점수도 얻지 못하고 화살도 낭비가 되어버리기 때문에 이 경우는 쓸모 없는 곳에 화살을 소모하는 경우가 될 것이다.

2번 경우를 보자. a개 보다 훨씬 더 많은 화살을 쏘는 경우를 생각해보자.

예를 들어서 어피치가 k점 과녁에 2개의 화살을 쐈다고 가정해보자. 이 때, 라이언이 k점 과녁에 5개의 화살을 쏠 필요가 있을까 ?? k점 과녁에 5개의 화살을 쏘나, 3개의 화살을 쏘나, 10개의 화살을 쏜아 똑같이 k점만 얻게 될 것이다.

왜냐하면, 어피치가 k점 과녁에 맞춘 화살의 갯수인 2개보다만 크면 라이언이 k점을 가져갈 수 있기 때문이다.

즉, 쓸데 없는 곳에 화살을 소모하지 않기 위해서는 어피치가 k점 과녁에 a개의 화살을 맞췄다고 가정했을 때, 라이언이 k점 과녁에 a + 1개의 화살을 맞추는 경우가 가장 쓸데 없는 곳에 화살을 소모하지 않는 경우가 될 것이다.

 

우리는 이 2가지에 초점을 맞추어서 라이언이 화살을 쏘는 것을 구현해볼 것이다.

 

#2. 화살 쏘기

그럼 #1의 이야기를 바탕으로 화살을 어떻게 쏠지에 대해서 이야기를 해보자.

먼저, 10점짜리 과녁부터 0점짜리 과녁까지 순차적으로 화살을 쏜다고 가정해보자.

우리는 K점 과녁에서 다음과 같은 선택지들이 생길 것이다.

 

1. 현재 남은 화살의 갯수 >= 어피치가 K점 과녁에 쏜 화살의 갯수 + 1

   - 이 경우에는 라이언에게 남은 화살의 갯수가 어피치가 K점 과녁에 쏜 화살의 갯수 보다 많기 때문에

     어피치가 K점 과녁에 쏜 화살의 갯수 + 1개를 쏘면 K점을 얻을 수 있게 된다.

     여기서 또 2가지 선택지가 생기게 된다.

     1. 어피치가 K점 과녁에 쏜 화살의 갯수 + 1 개 만큼의 화살을 쏘는 경우

     2. 화살을 쏘지 않고 넘어가는 경우

     위와 같이 2가지 선택지가 생기게 된다. #1에서 이야기 했듯이, 어피치가 K점 과녁에 쏜 화살의 갯수보다

     더 적은 화살의 갯수를 쏘거나, 훨씬 더 많은 화살을 쏘는 것은 의미가 없는 행동이다.

     그렇기 때문에 위와 같이 2개의 선택지만 생기게 될 것이다.

2. 현재 남은 화살의 갯수 <= 어피치가 K점 과녁에 쏜 화살의 갯수

   - 이 경우에는 선택지가 없다. 화살을 안쏘고 남은 화살이라도 챙겨 가는 것이 무조건 이득이다.

     왜냐하면, 남은 화살을 모두 쏘더라도 어피치가 K점 과녁에 쏜 화살의 갯수와 동일하거나 더 작기 때문에

     이 경우에는 전부 쏘더라도 결국 점수를 얻지 못하기 때문에 차라리 안 쏘는 것이 이득이다.

3. 0점 짜리 과녁일 경우

   - 우리는 처음에 가정을 10점부터 0점짜리 과녁까지 순차적으로 쏜다고 했었다.

     다른 과녁들은 화살을 쏘지 않고 넘어가는 그런 선택지가 있었지만 0점짜리 과녁에서는 그 다음 과녁으로

     넘어가는 선택지가 없다. 따라서, 0점짜리 과녁일 경우에는 어피치가 몇 개의 화살을 쐈는지와 상관없이

     남은 화살을 모두 쏴버려야 한다.

 

본인은 위의 3가지 경우에 대해서 완전탐색, 완전탐색 중에서도 깊이우선탐색(DFS)을 이용해서 구현해 주었다.

 

#3. 구현

마지막으로 구현에 관한 몇 가지 이야기만 하고 최종 소스코드만 보고 문제를 끝내도록 하자.

우리가 구해야 하는 것은 "라이엇이 화살을 쏘는 방법"을 구하면 된다.

그런데, 이 때 여러가지 조건이 있다.

어피치와 점수 차이가 가장 큰 방법을, 그런 방법이 여러개라면 가장 낮은 점수를 더 많이 맞힌 경우를 정답으로 구해주어야 한다. 그래서 본인은 이를 위해서 2가지 변수를 사용해 주었다.

"현재까지 구한 방법 중에서 점수 차이가 가장 큰 방법의 점수 차이"를 저장하는 int형 변수와

"현재까지 구한 방법 중에서 점수 차이가 가장 큰 방법"을 저장하는 vector, 이렇게 2개의 변수를 사용해 주었다.

이를 통해서 점수 차이를 비교하고, 점수 차이가 같은 방법이 여러개 있다면 0점 과녁부터 라이언이 쏜 화살의 갯수를 비교해주면서 정답을 구해 주었다.

 

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
int scoreResult = -1;
vector<int> ryan, apeach, ryanResult;
 
pair<int,int> calculate() {
    pair<int, int> score = { 0, 0 };
    for (int i = 0; i < 11; i++) {
        if (ryan[i] == apeach[i]) {
            if (ryan[i] == 0 && apeach[i] == 0) {
                continue;
            } else {
                score.second += (10 - i);
            }
        } else {
            if (ryan[i] > apeach[i]) {
                score.first += (10 - i);
            } else {
                score.second += (10 - i);
            }
        }
    }
    return score;
    
}
 
void check() {
    pair<int, int> score = calculate();
    int ryanScore = score.first;
    int apeachScore = score.second;
    int diff = ryanScore - apeachScore;
    if (diff <= 0) {
        return;
    }
 
    if (scoreResult == -1) {
        scoreResult = diff;
        ryanResult = ryan;
    } else {
        if (scoreResult == diff) {
            for (int i = 10; i >= 0; i--) {
                if (ryan[i] != 0 && ryanResult[i] == 0) {
                    ryanResult = ryan;
                    break;
                } else if (ryan[i] == 0 && ryanResult[i] != 0) {
                    break;
                } else if (ryan[i] != 0 && ryanResult[i] != 0) {
                    if (ryan[i] != ryanResult[i]) {
                        ryanResult = ryan[i] > ryanResult[i] ? ryan : ryanResult;
                        break;
                    }
                }
            }
        } else if (scoreResult < diff) {
            scoreResult = diff;
            ryanResult = ryan;
        }
    }
}
 
void dfs(int cnt, int idx, int n) {
    if (cnt == n) {
        check();
        return;
    }
 
    int curArrow = n - cnt;
    if (idx == 10) {    
        ryan[idx] = curArrow;
        dfs(cnt + curArrow, idx + 1, n);
        ryan[idx] = 0;
    } else {
        if (apeach[idx] + 1 <= curArrow) {
            ryan[idx] = apeach[idx] + 1;
            dfs(cnt + apeach[idx] + 1, idx + 1, n);
            ryan[idx] = 0;
        }
        dfs(cnt, idx + 1, n);
        
    }
}
 
vector<int> solution(int n, vector<int> info) {
    ryan.resize(11, 0);
    apeach = info;
    dfs(0, 0, n);
 
    if (scoreResult == -1) {
        ryanResult.push_back(-1);
    }
    return ryanResult;
}