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

문제

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

프로그래머스

---

🔎문제 해석

 

우선 문제를 읽고, DFS 혹은 백트래킹으로 풀어야겠다고 생각을 했습니다.

쭈욱 진행하다가, 만약 끝에 도달했을 때의 점수를 비교해서, 가장 큰 점수로 이기는 방법을 계속 찾아줬습니다.

문제에서는 만약 가장 큰 점수로 이기는 방법이 여러 가지라면, 특수한 조건을 부여했고, 그 조건도 그렇게 어려운 조건이 아닙니다.

문제에서 포인트는 이 문제를 DFS로 풀어야 한다는 것입니다.

 

우선 문제에서 가장 중요한 점은 항상 우위는 어피치가 가지고 있다는 뜻입니다.

만약 라이언과 어치피 둘다 10점에다가 3발을 적중시켰을 경우, 어치피가 점수를 가져가는 구조입니다.

그다음 중요한 점은 라이언에 과녁 적중의 결과에 따라 어치피의 점수도 달라진다는 점입니다.

따라서 화살을 N번 쏜 뒤, 점수를 따로따로 계산해줘야 합니다.

항상 어피치의 점수와 라이언의 점수는 그들의 결과에 영향을 받기 때문입니다.

 

아래 그림이 그 예시입니다.

우리는 그래서 N개의 화살을 쏜 뒤, 어피치와 라이언의 점수를 계산해줘야 합니다.

 

이렇게 어피치와 라이언의 점수차이가 가장 큰 방법을 선택해 주면 됩니다.

하지만 만약 점수차이가 같다면 어떻게 해야 할까요?

문제에서는 더 적은 점수의 과녁을 많이 맞춘 방법을 선택해줘야 합니다.

두 점수의 차이는 29로 동일하지만, 왼쪽 방식에서 라이언이 맞춘 가장 낮은 점수는 5점이고,

오른쪽 방식에서는 라이언이 맞춘 가장 낮은 점수는 4점입니다.

따라서 우리는 오른쪽 방법을 택할것입니다.

 

초기에 값을 0으로 설정해서, 만약 라이언이 한 번이라도 어피치를 이긴다면, 값을 업데이트해줍니다.

만약 함수 종료 시, 초기 값이 바뀌지 않았다면 라이언은 어피치를 이길 수 없습니다.

그때 -1을 리턴 해주면 됩니다.

 

기본적인 코드는 DFS이지만, 종료조건과 갱신조건을 잘 설정하면 쉽게 풀 수 있는 문제입니다.

 

💻코드

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
int total=0;
int result=0;
int rscore=0,ascore=0;
vector<int>temp;
vector<int> answer;
int sum_info(vector<int>info){
    int a=0;
    for(int i=0; i<=10; i++){
        if(info[i]>=temp[i] && info[i]!=0){ //횟수가 같을 시 어피치가 먹음.
            a+=10-i;
        }
    }
    return a;
}
void funct(vector<int>info,int depth,int res){
    if(depth<=11){
        if(res==0){
            int Ascore=sum_info(info); //어피치 점수
            int Rscore=0; //라이언 점수
            for(int i=0; i<=10; i++){
                if(temp[i]>info[i] && temp[i]!=0){
                    Rscore+=10-i;
                }
            }
            if(result<Rscore-Ascore){ 
                result = Rscore-Ascore;
                answer=temp;
            }
            else if(result==Rscore-Ascore){ //만약 같을 시
               for(int i=10; i>=0; i--){                  
                   if(temp[i] ==0 && answer[i]==0){ //둘다 0이면 다음 과녁을 확인
                       continue;
                   }
                   if(temp[i]>answer[i]){ //만약 새로운 방법이 적합한 경우
                       answer=temp;
                       break;
                   }
                   else //아니면 원래 방법을 저장
                       break;
               }
            }
            return;
        }
        else{
            for(int i=0; i<=res;i++){ //여기서 n번씩 돌려서 dfs실행.   
                
                temp[depth]=i;
                funct(info,depth+1,res-i);
                temp[depth]=0; //재귀를 탈출하면 초기화
            }
        }
    }
}

vector<int> solution(int n, vector<int> info) {

    answer.resize(11,0);
    temp.resize(11,0);
    funct(info,0,n);
    vector<int>aa;
    aa.push_back(-1);
    cout<<ascore<<" "<<rscore<<endl;
    if(result==0){
        return aa;
    }
    else
        return answer;
}

 

 

😀느낀 점

• N의 크기가 크지 않아서 충분히 DFS문제로 풀 수 있다고 생각했다.
• 하지만 종료조건을 잘못 적어서.. 조금 오래 걸렸다.