Programmers - 양궁대회

Programmers - 양궁대회

오늘의 두 번째 문제!!

요약하면 라이언과 어피치가 양궁 대회를 해서 라이언을 제일 큰 점수차로 이기게 해달라는 문제이다.
역시 카카오는 문제가 너무 길고 복잡하다..

처음에는 수학적으로 접근해 어떻게 쏴야 가장 큰 점수차가 될까.. 라는 생각을 하였는데, 아무리 고민해봐도 공식을 세울 방법이 생각이 나지 않았다.

결국 모든 경우를 다 해보는 브루트 포스 방식을 선택을 했고, 브루트 포스를 위해 DFS를 사용하였다!

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

using namespace std;

vector<int> result;
int t_max = -1;

// 라이언과 어피치의 점수를 계산해 
// 이전 답보다 점수 차이가 크면 답과 최대 점수 차이를 갱신해주었다
// 하나의 함수에 기능이 너무 많아 리팩토링을 해야 하지만.. 다음에..
void calc(vector<int> apeach, vector<int> ryan){
    int a = 0, r = 0;
    for(int i = 0; i < 11; i++){
        if(apeach[i] < ryan[i])
            r += 10 - i;
        else if(0 < apeach[i])
            a += 10 - i;
    }
    if(r - a > 0 && t_max < (r - a)){
        cout << r << " " << a << endl;
        result = ryan;
        t_max = r - a;
    }
    // 점수 차이가 같을 경우는 가장 낮은 곳을 많이 맞춘 것을 정답으로 인정해준다
    else if(r - a > 0 && t_max == (r - a)){
        for(int i = 10; i >=0; i--){
            if(result[i] != 0 || ryan[i] != 0){
                if(ryan[i] > result[i])
                    result = ryan;
                else if(ryan[i] == result[i])
                    continue;
                else
                    break;
            }
        }
    }
}

// dfs 함수 구현 부분이다
void dfs(int idx, int arrow, vector<int> apeach, vector<int>ryan){
	// 배열 끝까지 돌았거나, 화살을 다 썼다면 점수 계산을 시작!
    if(idx == 11 || arrow == 0){
    	// 배열을 끝까지 돌았지만, 화살을 다 안썼다면 모든 화살을 마지막 0점에 넣어준다
        if(arrow != 0){
            ryan[10] += arrow;
        }
        calc(apeach, ryan);
        return;
    }
    if(apeach[idx] < arrow){
        ryan[idx] += apeach[idx] + 1;
        arrow -= apeach[idx] + 1;
        dfs(idx + 1, arrow, apeach, ryan);
        arrow += apeach[idx] + 1;
        ryan[idx] -= apeach[idx] + 1;
    }
    dfs(idx + 1, arrow, apeach, ryan);
    
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer(1, -1);
    vector<int> ryan(11,0);
    result.resize(11,0);
    dfs(0, n, info, ryan);
    for(auto i : result){
        if(i != 0){
            answer = result;
        }
    }
    return answer;
}

테스트 케이스는 전부 맞았고, 제출 했을 때도 8번, 18번 테스트 케이스만 틀렸다고 나왔다...
분명 로직은 다 맞는것 같았는데 이해가 가지 않아 구글에 해답도 찾아봤지만, 살짝씩은 다르긴 해도 모두 비슷한 방식으로 푼 것을 확인할 수 있었다.

그렇게 20분째 이유를 몰랐었는데,

for(int i = 10; i >=0; i--)

이 부분에서 i++을 해놓고 못알아보고 있었던 것이다...
0부터 loop를 도는 for 문이 손에 익어서 자연스럽게 타이핑이 되었나보다...

앞으로는 조금 천천히 정확하게 코드를 짜도록 노력해야겠다!