프로그래머스 - 양궁대회

문제

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

프로그래머스

라이언이 최대 점수차로 (가장 적은 점수가 더 많은 결과로) 이길 수 있는 점수표를 만드는 문제였다.

 

문제 풀이

보자마자 완전탐색 문제인 것을 알았는데, 조건이 많아서 하나씩 구현하느라 꽤 걸렸다. dfs 종료조건에서 문제의 이런저런 조건을 다 충족시켜주고 이기는 경우가 없을 경우에는 asnwer에 -1을 넣어주면 된다.

 

처음에 점수 따는 경우와 안 따는 경우를 조건문으로 해서 사실은 안따는 경우는 돌아가지 않고 있었다. 따는 경우만 if로 해주고 안 따는 경우를 조건에서 빼 주니 원하는대로 모든 경우를 다 탐색했다. 이런 실수 조심하자!

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

using namespace std;


vector<int> lionScore, apeachScore; //라이언, 어피치 점수
vector<int> answerScore; //가장 차이 많이날 경우의 score
int aScore, lScore; //라이언, 어피치 현재 점수
int N; //총 화살 개수
int maxScore = 0; //가장 높은 점수차

void printVector(vector<int> v){
    for(int i=0;i<v.size();i++){
        printf("점수: %d 개수: %d\n", 10-i, v[i]);
    }
    printf("\n");
}

vector<int> scoreComparison(){ //answerScore와 lionScore 비교, 낮은 화살 더 많은 것 반환
    for(int i=10;i>=0;i--){
        if(answerScore[i] < lionScore[i]){
            return lionScore;
        }        
        else if(answerScore[i] > lionScore[i]) return answerScore;
    }
    return answerScore;
}

void dfs(int index, int lc, int ac, int nowArrow){ 
    //현재 점수 위치, 라이언 점수, 어피치 점수, 현재 화살 개수
    
    if(nowArrow > N) {
        //printf("화살촉 더 많이씀!\n");
        return;
    }
                      
    if(index == 11){ //종료조건, 비교
        //printf("종료조건!\n");
        //printf("어피치 점수: %d 라이언 현재 점수: %d  점수차: %d\n", ac, lc, lc-ac);
        if(lc <= ac) return;
        lionScore[10] += N-nowArrow;
        
        if((lc - ac) > maxScore){ //점수차 더 큰 경우
            maxScore = lc-ac;
            answerScore = lionScore;
        }
        else if((lc - ac) == maxScore){ //점수차 같을 경우 -> 가장 낮은 점수 비교
            answerScore = scoreComparison();
        }

        return;
    }
    
    //어피치 개수보다 1개 많이 해야 점수 따기 가능
    int nextArrow = apeachScore[index] +1; //던져야 하는 화살 수 
    int aScore = 0;
    if(apeachScore[index] > 0) aScore = 10-index;
    
    if(nextArrow + nowArrow <= N){ //점수 따기 가능
        lionScore.push_back(nextArrow);
        dfs(index+1, lc+ (10-index), ac, nowArrow+nextArrow);
        lionScore.pop_back();                
    }
    
    //점수 안 딸 경우
    lionScore.push_back(0);
    dfs(index+1, lc, ac+aScore, nowArrow);
    lionScore.pop_back();
          
}


vector<int> solution(int n, vector<int> info) { //info에는 10 9 8 ... 순으로 개수 저장
    vector<int> answer;    
    N=n;
    apeachScore = info;
    
    for(int i=0;i<n;i++){
        
    }
    dfs(0,0,0,0);
    if(maxScore == 0){
        answerScore.push_back(-1);        
    }
    return answerScore;
}