프로그래머스(카카오블라인드 테스트 2022) - 양궁대회

문제설명

---

1. 어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다.
2. 점수를 계산합니다.
   1. 과녁판은 아래 사진처럼 생겼으며 가장 작은 원의 과녁 점수는 10점이고 가장 큰 원의 바깥쪽은 과녁 점수가 0점입니다.
   2. 만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 단, a = b일 경우는 어피치가 k점을 가져갑니다. 
      k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져가는 것을 유의하세요. 또한 a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.
   3. 모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산합니다.
3. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.

< 입출력 예 >

4. 제한시간 안내

• 정확성 테스트 : 10초

---

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

 

첫번째 방법: 한 발 한 발 모든 경우의 수를 계산했더니 정확성 테스트에 걸렸다. (2^N)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> lyanCase;
int maxDiffrence=0;

void rec_calcurate(int n, vector<int> info, vector<int> lyan){   
    // 마지막 루프에서 점수 차이를 계산
    if(n <= 0) {
        int point_l = 0;
        int point_a = 0;
        for(int i=0; i<info.size(); i++){
            if(info[i] >= lyan[i] && info[i] > 0) point_a += 10-i;  
            if(info[i] < lyan[i] && lyan[i] > 0) point_l += 10-i; 
        }
        int diff = point_l - point_a;
        if(point_l > point_a && diff > maxDiffrence){
            lyanCase = lyan;
            maxDiffrence = diff;
        }
        return;
    }    
    
    // 각 화살 발사의 경우를 반복
    for(int i=0; i<info.size(); i++){
        vector<int> tempArr = lyan;
        tempArr[i] += 1;        
        rec_calcurate(n-1, info, tempArr);        
    }   
    return;
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
    
    vector<int> temp(info.size(),0);
    rec_calcurate(n, info, temp);
    
    if(maxDiffrence == 0) {
        answer = {-1};
    }else{
        answer = lyanCase;
    }
    return answer; 
}

 

두번째 방법: 각 '화살' 당 경우의 수(과녁 11가지)가 아니고 '과녁' 당 경우의 수(승,패 2가지) - 많이 줄어듦.(N^2)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int pointGrade = 11;
vector<int> lyanCase(pointGrade, 0);
int maxDiffrence=0;

// 라이언의 각 점수별 과녁의 승,패 경우를 쌓아서 가상의 라운드들을 만들고 어피치와 점수 비교. 
void rec_calculate(int loopCount, int arrowCount, vector<int> info, vector<int> lyan){   
    // 마지막에 점수차 계산 후 종료
    if(loopCount == 1) {
        int point_A=0;
        int point_L=0;
        bool checked = false;
        bool isSmallMuch_New = true;
        for(int i=0; i<pointGrade; i++){
            if(info[i] > 0 && info[i] >= lyan[i]) point_A += 10-i;
            if(info[i] < lyan[i]) point_L += 10-i;
            
            if(!checked && lyanCase[10-i] < lyan[10-i]){
                checked = true;
            }
            if(!checked &&lyanCase[10-i] > lyan[10-i]){
                checked = true;
                isSmallMuch_New = false;
            }
        }
        
        // 더 많은 점수차를 발생시킨 경우와 작은 점수의 과녁을 많이 맞춘 경우 비교.
        int diff = point_L-point_A;     
        bool canChange = diff > maxDiffrence
            ||(diff == maxDiffrence && isSmallMuch_New);
        if(canChange){
            maxDiffrence = diff;
            lyanCase = lyan;
            lyanCase[lyanCase.size()-1] = arrowCount;    
        }
        return;
    }
    
    int currentIndex = info.size() - loopCount;
    int arrowCount_A = info[currentIndex];
    int arrowCount_L = arrowCount;
    vector<int> winLyan = lyan;
    
    // 이길경우
    if(arrowCount_A < arrowCount){
        arrowCount_L = arrowCount - arrowCount_A - 1;
        winLyan[currentIndex] = arrowCount_A + 1;
        rec_calculate(loopCount-1, arrowCount_L, info, winLyan);        
    }
    
    // 질 경우
    rec_calculate(loopCount-1, arrowCount, info, lyan);    
        
    return;
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer = {-1};    
    vector<int> temp(pointGrade,0);   
    
    rec_calculate(pointGrade, n, info, temp);
    
    if(maxDiffrence > 0) answer = lyanCase;
    
    return answer;
}