[programmers] 92342번 - 양궁대회 (BFS, 2022 KAKAO BLIND RECRUITMENT)

1. 문제 및 예제

 

 DP인줄 알고 삽질만 두시간 했다가 도저희 감히 안잡혀서, 공식 문서 한 줄에서 힌트를 얻었다.

---

---

 이런 간단한 방법도 생각하지 못하다니... 난 아직 멀었나보다.. 

---

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

프로그래머스

---

2. 풀이과정

 

 문제에서는 경우의 수를 return하는 것이 아니라 어떤 과녁에 몇발의 화살을 맞췄는지를 반환해야하기 때문에 queue에 몇발을 맞췄는지에 대한 정보를 저장하는 배열을 추가하였다.

 

 queue에는 해당 과녁을 전혀 맞추지 않은 경우와 해다 과녁을 어피치보다 한 개 더 많이 맞춘 경우 이렇게 두가지로 상황을 나누어 추가해주면 된다.

 

 가장 낮은 점수를 많이 맞추는 경우를 반환해야하기 때문에 해당 과녁을 전혀 맞추지 않는 경우를 먼저 추가하고 순차적으로 queue에서 꺼내 사용한다.

 

 다음은 정답코드이다.

 

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

using namespace std;

bool is_lion_win(vector<pair<int, vector<int>>> cache) {
    for (int i = 0; i < cache.size(); i++) {
        if (cache[i].first > 0) 
            return false;
    }
    return true;
}

int is_max_unique(vector<pair<int, vector<int>>> cache) {
    //max 찾기
    int max = -1;
    int count_max = 0;
    for (int i = 0; i < cache.size(); i++) {
        if (max < cache[i].first)
            max = cache[i].first;
    }

    for (int i = 0; i < cache.size(); i++) {
        if (max == cache[i].first) {
            count_max++;
        }
    }


    if (max == 1) {
        return max;
    }
    else {
        return -1;
    }

}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
    int max = -1;
    vector<int> tmp = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    vector<pair<int, vector<int>>> cache;
    queue<
        pair<int, 
        pair<vector<int>, int>>> q;

    q.push(make_pair(0, make_pair(tmp, n)));

    while (!q.empty()) {

        int index = q.front().first;
        vector<int> target = q.front().second.first;
        int arraw = q.front().second.second;

        q.pop();

        //점수 계산하기
        if (arraw == 0 || index == 11) {
            
            int apache = 0;
            int lion = 0;

            for (int i = 0; i < 11; i++) {
                if (info[i] == 0 && target[i] == 0)
                    continue;
                if (info[i] >= target[i])
                    apache += 10 - i;
                else
                    lion += 10 - i;
            }

            cache.push_back(make_pair(lion - apache, target));
        }
        //0으로 할지 안 할지
        else {

            if (info[index] + 1 <= arraw) {
                int buff = target[index];
                target[index] = info[index] + 1;
                q.push(make_pair(index + 1, make_pair(target, arraw - (info[index] + 1))));
                target[index] = buff;
            }
            
            if (index == 10) {
                int buff = target[index];
                target[index] = arraw;
                q.push(make_pair(index + 1, make_pair(target, 0)));
                target[index] = buff;
            
            }else
                q.push(make_pair(index + 1, make_pair(target, arraw)));
        }
    }

    //라이언이 우승할 방법이 없는지를 체크
    if (is_lion_win(cache))
        return { -1 };

    for (int i = 0; i < cache.size(); i++) {
        if (max == -1) {
            max = cache[i].first;
            answer = cache[i].second;
        }
        else if(max <= cache[i].first){
            max = cache[i].first;
            answer = cache[i].second;
        }
    }

    return answer;
}

 

 

3. 결어

 

 너무 복잡한 알고리즘이 아닌 간단한 방식으로 먼저 풀어볼 생각을 하는 것이 중요하다는 것을 알게 되었다.