[프로그래머스/C++] 알고리즘 - 양궁대회

안녕하세요! 테크지니어22입니다.

오늘은 프로그래머스 알고리즘 - 양궁대회 를 풀어보도록 하겠습니다.

 

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

프로그래머스

 

[문제 접근]

처음에 얼핏 생각하면 과녁 점수마다 0~10발 맞힐 수 있으니 10^11이니 완전탐색이 불가능하고 그리디 알고리즘으로 접근해야하는 거아닌가라고 생각을 했습니다. 그러나 모든 과녁점수의 맞힌 횟수의 합이 n이기 때문에 시간복잡도가 현저히 낮다는 사실을 알 수 있고, 정확성 테스트를 위하 시간제한이 10초이고, n = 10이하여서 완전탐색을 생각했습니다.

완전탐색을 하기 위해 이중for문을 이용하여 접근을 시도했는데 잘되지 않았습니다. 이때 재귀를 이용한 완전탐색이 떠올랐고, 이를 이용하여 풀었습니다.

 

[풀이 전략]

1. 재귀 함수를 만듭니다.

2. 재귀 함수를 이용하여 라이언의 모든 경우의 수를 col이라는 벡터에 저장합니다.

3. 라이언의 모든 경우의 수를 확인하면서 스코어차이가 가장 큰 경우를 answer에 저장합니다. (이때, 제약조건들을 걸어줘야합니다)

4. answer가 비어있으면 -1을 삽입합니다.

 

[코드]

#include <string>
#include <vector>
using namespace std;

int num ; 
vector<int> tmp ; 
vector<vector<int>> col ;
void dfs(int cnt,int val) {
    if(cnt == 11) {
    col.push_back(tmp);
        return;}
    
    for(int i = 0 ; i <= val ; i++){
        if(val >= i) {
            tmp.push_back(i);
            dfs(cnt+1, val - i);
            tmp.pop_back();
        }
    }
    
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
    int dif = 0 ; 
    num = n ;  
    dfs(0,n);
    
    for(auto v : col) {
        int score1 = 0 ;
        int score2 = 0; 
           for(int i = 0 ; i < 11 ; i++){
        if(info[i] < v[i]) {
            score2 += 10-i;
        } else { 
            if(info[i] == 0 && v[i] == 0) continue;
                score1 += 10-i;
        }
    } 
        if(score1 < score2) {
             if(dif < score2 - score1) {
                 dif = score2 - score1 ;
                 answer = v;
             } else if(dif == score2 -score1) {
                 for(int i = 10 ; i>= 0; i--){
                     if(answer[i] < v[i]) {
                         answer = v ; 
                         break;
                     } else if(answer[i] > v[i]) break; 
                 }
             }
        }
    }
    if(answer.empty()) answer.push_back(-1);
    
    return answer;
}

 

[배울 점]

- 완전탐색에서 재귀를 이용하는 풀이 생각해보기. -> 그래프가 아니어도 재귀를 이용한 dfs풀이가 있다는 사실 기억하기.