[프로그래머스] Level 2. 양궁 대회

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

프로그래머스

해결 방법

✅ 완전 탐색(DFS)과 백트래킹을 활용한 C++ 풀이
✅ 점수 차이를 최대로 만들면서 낮은 점수를 더 많이 맞히는 경우 고려

 

• 0점부터 10점까지 11개의 점수대를 탐색하며 라이언이 해당 점수를 가져갈지 말지 결정한다.
• 두 가지 선택이 가능:
  1. 라이언이 어피치보다 1발 더 맞혀 점수를 가져감
  2. 라이언이 그 점수를 포기하고 다음 점수대로 이동
• 탐색을 마친 후, 라이언의 점수와 어피치의 점수를 비교하여 최적의 경우를 찾는다.

1 ) 점수차이 계산하는 get_diff() 함수

int get_diff(){
    int apeach = 0, ryon = 0;
    for(int i = 0; i <= 10; i++){
        if(ryons[i] == 0 && apeaches[i] == 0) continue;
        if(ryons[i] > apeaches[i]) ryon += (10 - i);
        else apeach += (10 - i);
    }
    return ryon - apeach;
}

 

2 ) 현재 라이언의 점수가 답으로 갱신해도 되는지 검사하는 is_valid() 함수

bool is_valid(){
    int diff  =  get_diff();
    if(diff <=0 || diff < max_diff) return false;
    if(diff > max_diff) return true;
    
    //점수가 같은 경우, 가장 낮은점수가 높은 점수가 채택된다
   
    for(int i=10;i>=0;i--){
        if(ryons[i]>answer[i])return true;
        else if(ryons[i]<answer[i]) return false;
    }
    
    return false;
}

 

 

전체코드

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

using namespace std;
vector<int> answer;

vector<int> ryons; //라이언의 과녁
vector<int> apeaches; //어피치 과녁

int max_diff = -1; //점수차이


int get_diff(){
    int apeach = 0; int ryon =0;
    for(int i=0; i<apeaches.size(); i++){
        if(ryons[i] == 0 && apeaches[i] == 0) continue;
        else if(ryons[i]<=apeaches[i])apeach += 10-i;
        else ryon += 10-i;
    }
    return ryon - apeach;
}

bool is_valid(){
    int diff  =  get_diff();
    if(diff <=0 || diff < max_diff) return false;
    if(diff > max_diff) return true;
    
    //같은 경우;
    
    for(int i=10;i>=0;i--){
        if(ryons[i]>answer[i])return true;
        else if(ryons[i]<answer[i]) return false;
    }
    
    return false;
}

void go_search(int idx, int arrow){
    if(idx == 11 || arrow == 0){
        ryons[10] += arrow;  //남은화살을 제일 점수낮은곳에 쏨.

        if(is_valid()){
            max_diff = get_diff();
            answer = ryons;
        }
        //복구
        ryons[10] -= arrow;
        return;
    }
    
    //화살을 쏠 게 남아있다면
    if(arrow > apeaches[idx]){
        ryons[idx] = apeaches[idx]+1;
        go_search(idx+1, arrow - ryons[idx]);
        ryons[idx] = 0;
    }
    
    //화살을 더이상 쏠 게없다면
    go_search(idx+1,arrow);
}
vector<int> solution(int n, vector<int> _info) {
    ryons.resize(_info.size(),0);
    apeaches = _info;

    go_search(0,n);
    
    if(max_diff == -1) return vector<int>(1,-1);
    return answer;
}

 

 

마무리하며

Level 2인데도, 완전탐색은 어렵다. ㅠㅠ  두가지 어려운 점이 있었다.

 

 

1. for문을 사용하지 않고, 재귀 DFS를 사용했다. 과녁을 맞추지 않는 경우를 go_search() 로 한번 더 호출한 점.

 

보통 완전탐색의 경우 FOR문을 사용해서 과녁을 쏜다/안쏜다로 검사한다.  그런데 여기에서는 for문을 사용하지 않기 때문에, 명시적으로 화살을 쏘지 않을 경우에 대한 재귀도 추가해야 한다.

for 문을 사용한 DFS의 특징은 다음과 같다.

 

장점

✔ 코드가 직관적 → for 문을 사용하면 과녁을 순회하는 방식이 한눈에 보임.
✔ 탐색 순서가 명확 → i = start부터 i < 11까지 순회하기 때문에 idx 기반 탐색이 명확.

 

단점

❌ 점수를 포기하는 경우의 탐색이 중복될 수 있음.

• 점수를 포기하는 경우 go_search(start+1, arrow);을 호출하는데, 이 과정에서 이미 for 문에서 포기하는 경우가 포함될 가능성이 있음.
  ❌ 탐색할 경우의 수가 많아질 수도 있음.
• 모든 i에 대해 ryons[i]를 설정하는데, 불필요한 탐색이 증가할 가능성이 있음

결론: for 문 DFS도 가능하지만, 기존 DFS가 더 최적화됨!

 

1️⃣ for 문을 활용한 DFS도 문제 해결이 가능하지만, 불필요한 연산이 늘어날 가능성이 있음.
2️⃣ 기존 DFS는 점수를 가져가는 경우 & 포기하는 경우를 명확하게 나누어서 탐색하기 때문에 더 효율적일 수 있음.
3️⃣ 그러나 for 문 DFS는 코드가 직관적이므로, 이 방식이 더 익숙한 사람에게는 장점이 될 수도 있음.

 

 

2. 남은 화살 처리하기

 

최적의 해를 갱신할 때, 만약 남은 arrow가 있을 경우, 0점짜리 과녁에 남은 화살을 모두 넣은  뒤, 만약 diff가 동일하다면 가장 낮은 점수 과녁이 많은 경우를 선택해야 한다. 이 부분에서 0점짜리 과녁에 남은 화살을 모두 넣었다 빼는 부분이 어려웠다. 

 

 

답을 알면 쉬운데, 알아채기 힘든것이 알고리즘인듯