프로그래머스 문제 - 양궁대회

프로그래머스 양궁대회 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

라이언과 어피치가 0~10까지의 점수를 가진 과녁을 두고 양궁을 진행합니다.
둘 중 똑같은 점수를 맞췄을 때 화살을 더 많이 맞춘 쪽이 점수를 획득하며 같을 경우 어피치가 점수를 가져가게 됩니다.
또한 둘 다 맞추치 못한 과녁 점수는 계산하지 않습니다.
어피치 먼저 모든 화살을 맞추었을 때 라이언이 가장 큰 점수차로 이길 수 있는 경우를 구해야합니다.

문제 풀이

총 과녁은 맞추지 않는 0점을 제외하고 1~10점까지 10가지이며, 점수당 얻거나 얻지 않을 수 있습니다.
즉, 점수를 얻을 수 있는 모든 경우의 수를 계산하더라도 수가 많지 않기 때문에 완전탐색으로 문제를 해결할 수 있습니다.
1가지 점수만 얻는 경우부터 하나씩 올라가 모든 점수를 먹는 경우까지 순열을 통해 모두 탐색해준 후, 화살을 쏘는 횟수가 일치하며 점수 차이가 제일 큰 경우를 찾아주면 됩니다.
이때 주의할 점은 점수가 같으면 적은 점수를 맞춘 횟수가 많은 경우를 선택해야 합니다.
이 부분은 과녁에 맞춘 화살이 주어진 화살보다 적게 사용하여 맞출 경우 나머지 화살을 0점으로 만들어 제일 적은 점수를 늘림으로써 경우의 수를 만들어 줄 수 있습니다.
예를 들어 어피치가 5개의 화살로 과녁을 맞춘 화살이 [2,1,1,1,0,0,0,0,0,0,0]으로 주어졌을 때 라이언이 9점과 8점만을 얻기 위해서는
[0,2,2,0,0,0,0,0,0,0,0]처럼 화살을 쏠 수 있습니다.
하지만 쏴야하는 화살이 5개이기에 남은 화살을 0점으로 쏴서 [0,2,2,0,0,0,0,0,0,0,1]이라는 경우의 수를 만들 수 있습니다.
우승할 방법이 없거나 비겼을 경우 -1을 출력해주면 됩니다.

전체 코드

순열을 잘 사용하여 완전탐색을 진행하면 쉽게 풀 수 있는 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
    vector<int> arr(10, 1);
    vector<int> copyArr;
    vector<int> result;
    
    arr[0] = 0;
    for(int i = 0; i < 10; i++)
    {
        arr[i] = 0;
        copyArr = arr;
        do{
            vector<int> v(13, 0);
            for(int j = 0; j < 10; j++) //어피치 점수와 라이언 점수 차이 및 과녁에 맞춘 화살 계산
            {
                if(copyArr[j] == 0)
                {
                    v[j] += info[j] + 1;
                    v[11] += info[j] + 1;
                    v[12] += 10 - j;
                }else if(copyArr[j] == 1 && info[j] != 0){
                    v[12] -= 10 - j;
                }
            }
            if(v[11] <= n && v[12] >= 0) //점수 차가 더 큰 경우 검색
            {
                v[10] = n - v[11];
                v[11] += v[10];
                if(result.empty() || result[12] < v[12])
                    result = v;
                else if(result.empty() || result[12] == v[12])  //만약 점수가 같다면 더 적은 점수를 맞췄는지 확인
                {
                    for(int j = 9; j >= 0; j--)
                    {
                        if(result[j] < v[j]){
                            result = v;
                            break;
                        }else if(result[j] > v[j])
                            break;
                    }
                }
            }
        } while(next_permutation(copyArr.begin(), copyArr.end()));
    }
    
    if(result.size() == 0 || result[12] == 0)   //무승부거나 값이 없을 때 -1
        answer.push_back(-1);
    else
        for(int j = 0; j <= 10; j++)
        {
            answer.push_back(result[j]);
        }
    
    return answer;
}

출저

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