[프로그래머스 C++] 양궁대회

 

[프로그래머스 C++] 양궁대회

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

 

해결전략

 

완전탐색 Brute Force

 

문제를 읽고 완전탐색 문제라는것은 파악했다. 하지만 어려웠던 점이 2가지 있었다. 이 부분은 생각이 나지 않아 문제 게시판을 읽고 알게 되었다. 

 

 

 

< 모든 점수판을 확인 || 화살을 모두 사용한 경우 >

DFS가 끝나는 시점에 아래 부분을 생각하기 힘들었다.

•  ryan[ 10 ] = remain;  // 남은 화살은 무조건 가장 낮은 점수에 사용 

if문에 들어가는 경우 중 ' remain == 0 ' 인 경우는 코드 상 아무런 영향을 미치지 않는다.  

 

if문에 들어가는 경우 중 ' k == 11 ' 인 경우 중 화살이 남은 경우, 화살을 소모해야 하므로 ryan[10]에 남은 화살을 모두 쏘는 것이다.

 	if (k == 11 || remain == 0) // 모든 점수판을 확인했거나 화살을 모두 사용한 경우
    { 
        ryan[10] = remain; // 남은 화살은 무조건 가장 낮은 점수에 사용
    	Cal(); // 점수 계산
        ryan[10] = 0; // 다음 경우의 수를 위해 초기화
        return;
    }

 

 

 

< 점수차가 같은 경우 >

아래와 같이 가장 낮은 번호부터 체크하면서 가장 낮은 수가 들어갔는지 확인해야 한다. 

bool GivenLogic()
{
	for (int i = 10; i >=0; i--){
        if (answer[i] < ryan[i]) return true; // 라이언이 더 많은 점수를 획득한 경우 true 반환
        if (answer[i] > ryan[i]) return false; // 어피치가 더 많은 점수를 획득한 경우 false 반환
	}
}

 

 

---

 

 

정답 코드

 

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> apeach(11), ryan(11); // 어피치와 라이언의 점수판
vector<int> answer;
int maxDiff; // 라이언과 어피치의 점수 차이의 최대값
 
bool GivenLogic()
{
	for (int i = 10; i >=0; i--){
        if (answer[i] < ryan[i]) return true; // 라이언이 더 많은 점수를 획득한 경우 true 반환
        if (answer[i] > ryan[i]) return false; // 어피치가 더 많은 점수를 획득한 경우 false 반환
	}
}
 
void Cal(){
    int apeachScore = 0, ryanScore = 0; // 어피치와 라이언의 점수를 계산하기 위한 변수
 
    for (int i = 0; i <= 10; i++){
        if (apeach[i] == 0 && ryan[i] == 0) continue; // 양쪽 모두 점수를 얻지 못한 경우 건너뛰기
 
    	if (apeach[i] >= ryan[i]){
            apeachScore += (10 - i); // 어피치가 해당 점수를 가져가는 경우
        }
        else if (apeach[i] < ryan[i]){
            ryanScore += (10 - i); // 라이언이 해당 점수를 가져가는 경우
        }
    }
 
    // 어파치가 이긴 경우
    if (apeachScore >= ryanScore) {
        return;
    }
 
    // 라이언이 이긴 경우, 값을 업데이트
    if (maxDiff < ryanScore - apeachScore)
    {
        maxDiff = ryanScore - apeachScore; // 점수차 업데이트
        answer = ryan;
    }
    else if (maxDiff == ryanScore - apeachScore) // 점수차가 이전이랑 같은 경우
    {
	    if(GivenLogic()) // 작은 값이 더 많은지 확인
	    {
            maxDiff = ryanScore - apeachScore; // 점수차 업데이트
            answer = ryan;
	    }
    }
 
}
 
void DFS(int k, int remain) // k: 점수판 위치(10,9,8,...,1,0 순서), remain: 남아있는 화살 수
{
    if (k == 11 || remain == 0){ // 모든 점수판을 확인했거나 화살을 모두 사용한 경우
        ryan[10] = remain; // 남은 화살은 무조건 가장 낮은 점수에 사용
    	Cal(); // 점수 계산
        ryan[10] = 0; // 다음 경우의 수를 위해 초기화
        return;
    }
 
    if (remain > apeach[k]){ // 어피치보다 많은 화살을 쏘아 점수를 가져갈 수 있는 경우
        ryan[k] = apeach[k] + 1;
        DFS(k + 1, remain - (apeach[k] + 1)); // 다음 점수판 확인
        ryan[k] = 0; // 다음 경우의 수를 위해 초기화
    }
    DFS(k + 1, remain); // 현재 점수판에서 화살을 사용하지 않고 다음 점수판 확인
}
 
vector<int> solution(int n, vector<int> info) {
 
    apeach = info; // 어피치의 점수판 초기화. info 대신 apeach를 전역으로 사용하기 위해 사용.
 
    DFS(0, n);
 
    if (answer.size() == 0) answer.push_back(-1); // 라이언이 이길 수 있는 방법이 없는 경우
    
    return answer;
}

 

 

---