프로그래머스 - 양궁대회 (C++)

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

프로그래머스

 이번 문제는 어피치의 활을 쏜 결과가 주어졌을 때, 라이언이 어떻게 화살을 쏴야 어피치에게 가장 큰 점수차로 이길 수 있을지를 구하는 문제이다. 그리고 이 가장 큰 점수차를 구하는 데에 있어서 조건이 있다. 그 조건은 가능한 경우 중, 가장 낮은 점수를 더 많이 맞힌 경우를 구해야 한다는 것이다. 그렇기에 결국, 라이언이 점수를 획득할 수 있는 모든 경우의 수를 따져봐야 한다. 그렇다고 10점에 1발인 경우, 10점에 2발인 경우 등, 정말로 모든 경우의 수를 고려한다면 매우 큰 시간이 필요할 것이다. 따라서, 어느 정도의 제한이 필요하다.

 문제에 점수를 획득하기 위한 조건으로 '만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 단, a = b일 경우는 어피치가 k점을 가져갑니다. k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져가는 것을 유의하세요. 또한 a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.'가 있다. 즉, 어피치가 명중시킨 화살보다 한 개라도 더 많이 명중시킨다면 그 점수를 획득할 수 있다는 뜻이다. 그렇기에 점수 n을 획득할 수 있는 경우는 현재 남은 화살의 개수가 어피치가 n점에 명중시킨 화살 수 + 1보다 큰지 고려하면 된다. 이를 이용해 고려한 풀이 방법은 다음과 같다.

1. 문제를 풀기 위해 필요한 변수들의 값을 초기화한다.
2. 라리언이 득점할 수 있는 모든 경우를 체크한다.
   1. 만약, 득점에 필요한 화살 수(현재 점수의 어피치 화살 수 + 1)보다 많은 화살을 가지고 있다면, 득점할 수 있는 기회이므로 이 점수를 획득한 후의 상황을 점검한다.
   2. 그리고 이 점수를 획득하지 않고 진행하는 경우도 확인한다.
   3. 만약 현재 득점을 고려 중인 점수가 0점이면서, 남아있는 화살이 있는 경우 0점에 모든 화살을 명중시킨다. 왜냐하면 문제 조건에서 '가장 낮은 점수를 더 많이 맞힌 경우'를 구하라고 했기 때문이다.
   4. 만약, 모든 점수에 대해 고려가 끝난 상황ㅇ라면, 라이언의 점수와 어피치의 점수를 비교한다.
      1. 만약, 라이언의 점수가 어피치의 점수보다 크다면, 답을 갱신할 수도 있는 상황이다.
      2. 만약, 기존의 점수차보다 현재의 점수차가 더 크다면, 갱신할 수 있는 상황이다.
      3. 만약, 기존의 점수차와 같으면서 문제의 조건인 '가장 낮은 점수를 더 많이 맞힌 경우'라면, 이 역시 갱신할 수 있다.
   5. 만약, 점수가 갱신되지 않았다면, 라이언이 어피치를 이길 수 없는 상황이라는 뜻이므로, 문제의 조건에 따라 { -1 }을 반환하고, 아니라면 구한 답을 반환한다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 11

int maxScoreDiff = -1;		// 라이언과 어피치의 가장 큰 점수 차이
vector<int> lionArrow;		// 라이언의 화살
vector<int> apeachArrow;	// 어피치의 화살 (문제에서 주어짐))
vector<int> answer;			// 답

bool CanRenew(int curScoreDiff)
{	
	// 2-4-2. 만약, 기존의 점수차보다 더 크다면 당연히 갱신할 수 있으므로 true를 반환한다.
	if (curScoreDiff > maxScoreDiff)
		return true;

	// 2-4-3. 만약, 기존의 점수차와 같은 점수차라면 
	// 문제의 조건인 '가장 낮은 점수를 더 많이 맞힌 경우'인지 확인한다.
	// 이를 통해 갱신가능하다면 true를 반환한다.
	if (curScoreDiff == maxScoreDiff)
	{
		for (int score = 0; score <= 10; ++score)
		{
			if (answer[score] < lionArrow[score])
				return true;
			else if (answer[score] > lionArrow[score])
				return false;
		}
	}
	
	return false;	// 결국 갱신할 수 없는 경우이므로 false 반환
}

// 10점부터 시작해서 0점까지 활을 쏘는 경우를 검사하는 함수
void ScoreCheck(int leftArrow, int score)
{
	// 2-4. 만약, 모든 점수에 대해 고려를 끝낸 상황이라면, 라이언의 점수와 어피치의 점수를 비교한다.
	if (score < 0)
	{	
		int lionScore = 0;
		int apeachScore = 0;

		for (int score = 0; score <= 10; ++score)
		{
			if (lionArrow[score] == 0 && apeachArrow[score] == 0)
				continue;

			if (lionArrow[score] > apeachArrow[score])
				lionScore += score;
			else
				apeachScore += score;
		}

		// 2-4-1. 만약, 라이언의 점수가 어피치의 점수보다 크다면, 
		// 답이 될 수 있는 상황이다.
		if (lionScore > apeachScore)
		{
			int curScoreDiff = lionScore - apeachScore;

			// 2-4-4. 만약, 답을 갱신할 수 있다면 갱신한다.
			if (CanRenew(curScoreDiff))
			{
				maxScoreDiff = curScoreDiff;
				answer = lionArrow;
			}
		}

		return;
	}

	// 2-3. 만약 현재 고려중인 점수가 0점이면서, 남은 화살이 있는 경우
	// 0점에 모든 화살을 쏜다.
	// 왜냐하면 문제 조건에서 '가장 낮은 ㅈ머수를 더 많이 맞힌 경우'를 구하라고 했기 때문이다.
	if (score == 0 && leftArrow > 0)
	{
		lionArrow[0] = leftArrow;
		ScoreCheck(0, score - 1);
		lionArrow[0] = 0;
	}

	// 2-1. 만약 득점에 필요한 화살 수(현재 점수의 어피치화살 수 + 1)보다 많은 화살을 가지고 있다면
	// 득점할 수 있는 기회이므로 이 점수를 획들한 후의 상황을 점검한다.
	int curRequiredArrow = apeachArrow[score] + 1;

	if (leftArrow >= curRequiredArrow)
	{
		lionArrow[score] = curRequiredArrow;
		ScoreCheck(leftArrow - curRequiredArrow, score - 1);
		lionArrow[score] = 0;
	}

	// 2-2. 이 점수를 획득하지 않고 진행하는 경우도 확인한다.
	ScoreCheck(leftArrow, score - 1);
}

vector<int> solution(int n, vector<int> info) 
{	
	// 1. 문제를 풀기 위해 필요한 변수들의 값을 초기화한다.
	maxScoreDiff = -1;

	answer.clear();
	lionArrow.clear();
	apeachArrow.clear();

	for (int i = 0; i < MAX; ++i)
	{
		answer.push_back(0);
		lionArrow.push_back(0);
		apeachArrow.push_back(0);
	}

	for (int infoIdx = 0, score = 10; infoIdx < info.size(); ++infoIdx, --score)
		apeachArrow[score] = info[infoIdx];

	// 2. 라이언이 득점할 수 있는 모든 경우를 체크한다.
	ScoreCheck(n, 10);

	// 3. 만약, 최대 점수차가 갱신되지 않았다면,
	// 어피치를 이길 수 없는 상황이라는 뜻이므로 
	// 문제의 조건에 따라 { -1 }을 반환한다.
	if (maxScoreDiff == -1)
		return { -1 };

	// 아니라면 answer를 reverse하여 반환한다.
	// 왜냐하면 answer[10]은 10점의 화살 개수인데, 
	// 문제에서 요구하는 답은 거꾸로 answer[0]에 10점의 화살 개수가 담긴 형태이기 때문이다.
	reverse(answer.begin(), answer.end());

	return answer;
}