[C++, 완전탐색] 프로그래머스 양궁대회

문제

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

코딩테스트 연습 - 양궁대회

 

풀이

완전탐색 문제이다. 

총 11개의 점수(0점 ~ 10점) 에서 라이언이 해당 점수를 선택하냐 선택하지 않느냐로 나눌 수 있다.

구현이 쉬운 dfs로 풀이하였다.

 

해당 문제에서 주의해야 할 점이 있다.

문제를 꼼꼼히 읽어보면 알 수 있는데 예시에도 나와있듯이 

• 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해야 한다.
• [0,0,2,3,4,1,0,0,0,0,0]과 [9,0,0,0,0,0,0,0,1,0,0]를 비교하면[9,0,0,0,0,0,0,0,1,0,0]를 return 해야 한다.

그냥 단순히 dfs를 돌려서 나중에 나오는 경우가 답이라고 생각해 풀었더니 다시 읽어보고 문제를 찾는데 20분 더 걸렸다.ㅜㅜ 문제를 꼼꼼히 읽자.

 

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

using namespace std;

vector<int> g_answer;
int g_maxGap;



bool compLastScore(vector<int>& lion) {
	if (g_answer.empty())
		return true;
	for (int i = 10; i >= 0; i--) {
		if (lion[i] > g_answer[i]) return true;
		if (lion[i] < g_answer[i]) return false;
	}
	return true;
}

void calScore(vector<int>& lion, vector<int>& apeche)
{
	int lionScore = 0, apecheScore = 0;


	for (int i = 0; i < apeche.size(); i++) {
		if (lion[i] > 0 || apeche[i] > 0) {
			if (lion[i] > apeche[i]) {
				lionScore += 10 - i;
			}
			else {
				apecheScore += 10 - i;
			}
		}
	}
	int scoreGap = lionScore - apecheScore;
	if (scoreGap > 0 && ((g_maxGap < scoreGap)|| (g_maxGap == scoreGap && compLastScore(lion)))) {
		g_maxGap = scoreGap;
		g_answer = lion;
	}

}

// 0 1 2 3 4 5 6 7 8 9 10 (11개)
void dfs(int depth, int arrowNum, vector<int>& lion, vector<int>& apeche) {
	if (depth == 10 || arrowNum == 0) {
		if (arrowNum > 0)
			lion[10] = arrowNum;
		calScore(lion, apeche);
		if (arrowNum > 0)
			lion[10] = 0;
		return;
	}
	//선택
	if (arrowNum >= apeche[depth] + 1) {
		lion[depth] = apeche[depth] + 1;
		dfs(depth + 1, arrowNum - lion[depth], lion, apeche);
	}
	//no 선택
	lion[depth] = 0;
	dfs(depth + 1, arrowNum, lion, apeche);
}

vector<int> solution(int n, vector<int> info) {
	vector<int> lion = { 0,0,0,0,0,0,0,0,0,0,0 };

	dfs(0, n, lion, info);

	if (g_answer.empty())
		g_answer.push_back(-1);
	return g_answer;
}