[프로그래머스 Level 2] 양궁대회(C++)

코딩테스트 연습 - 양궁대회 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

info의 길이는 고정으로 11이므로 dfs를 돌려서 이기는 경우와 지는 경우로 설정해주면 된다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> ans;
vector<int> in;
int maxCha=0;

void dfs(vector<int> v, int depth, int remind) {
	if (remind == 0) {
		int total = 0;
		int another = 0;
		for (int i = 0; i < 11; i++) {
			if (v[i] != 0) {
				total += 10 - i;
			}
			else {
				if (in[i] != 0) {
					another += 10 - i;
				}
			}
		}
		if (maxCha < total - another) {
			maxCha = total-another;
			ans = v;
		}
		else if ((maxCha != 0) && (maxCha == total - another)) {
			for (int i = 10; i >= 0; i--) {
				if (v[i] > ans[i]) {
					ans = v;
					break;
				}
				else if (v[i] == ans[i])
					continue;
				else {
					break;
				}
			}
		}
		return;
	}
	if (depth == 11) {
		if (remind != 0) {
			v[10] += remind;
		}
		int total = 0;
		int another = 0;
		for (int i = 0; i < 11; i++) {
			if (v[i] != 0) {
				total += 10 - i;
			}
			else {
				if (in[i] != 0) {
					another += 10 - i;
				}
			}
		}
		if (maxCha < total - another) {
			maxCha = total-another;
			ans = v;
		}
		else if ((maxCha != 0) && (maxCha == total - another)) {
			for (int i = 10; i >= 0; i--) {
				if (v[i] > ans[i]) {
					ans = v;
					break;
				}
				else if (v[i] == ans[i])
					continue;
				else {
					break;
				}
			}
		}
		return;
	}
	dfs(v, depth + 1, remind);

	if (remind > in[depth]) {
		v[depth] = in[depth] + 1;
		remind = remind - in[depth] - 1;
		dfs(v, depth + 1, remind);
	}
}

vector<int> solution(int n, vector<int> info) {
	vector<int> answer;
	in = info;
	vector<int> tmp(11, 0);
	dfs(tmp, 0, n);
	if (ans.empty())
		answer.push_back(-1);
	else {
		answer = ans;
	}
	return answer;
}