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

문제 설명

카카오배 양궁대회 결승전에 라이언과 어피치가 대결한다.

어피치가 먼저 화살을 모두 쏜 후, 라이언이 화살을 모두 쐈을 때, 라이언이 큰 점수 차이로 이기는 방법을 구하는 문제이다. (방법이 여러개라면, 가장 낮은 점수를 더 많이 맞히 경우가 정답이다.)

 

점수 계산법

  -  k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져감.

     10점에 어피치가 3발, 라이언이 2발 쐈다면 어피치가 10점을 얻게 되고 라이언은 0점을 얻게된다.

     라이언이 점수를 획득하기 위해서는 어피치보다 +1개를 쏴야 점수도 얻고 불필요한 화살 소모를 줄일 수 있다.

     효율적으로 점수를 획득해야 한다.

    

     불필요한 화살 소모는 다음과 같다.

     1) K점 과녁에 a개 이하의 화살을 쏘는 경우

     2) K점 과녁에 a개 보다 훨씬 더 많은 화살을 쏘는 경우

 

 

제한 사항

• 1 ≤ n ≤ 10
• info의 길이 = 11
  • 0 ≤ info의 원소 ≤ n
  • info의 원소 총합 = n
  • info의 i번째 원소는 과녁의 10 - i 점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)
• 라이언이 우승할 방법이 있는 경우, return 할 정수 배열의 길이는 11입니다.
  • 0 ≤ return할 정수 배열의 원소 ≤ n
  • return할 정수 배열의 원소 총합 = n (꼭 n발을 다 쏴야 합니다.)
  • return할 정수 배열의 i번째 원소는 과녁의 10 - i 점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)
  • 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
    • 가장 낮은 점수를 맞힌 개수가 같을 경우 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
    • 예를 들어, [2,3,1,0,0,0,0,1,3,0,0]과 [2,1,0,2,0,0,0,2,3,0,0]를 비교하면 [2,1,0,2,0,0,0,2,3,0,0]를 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 해야 합니다.
• 라이언이 우승할 방법이 없는 경우, return 할 정수 배열의 길이는 1입니다.
  • 라이언이 어떻게 화살을 쏘든 라이언의 점수가 어피치의 점수보다 낮거나 같으면 [-1]을 return 해야 합니다.

입출력 예

n	info	result
5	[2,1,1,1,0,0,0,0,0,0,0]	[0,2,2,0,1,0,0,0,0,0,0]
1	[1,0,0,0,0,0,0,0,0,0,0]	[-1]
9	[0,0,1,2,0,1,1,1,1,1,1]	[1,1,2,0,1,2,2,0,0,0,0]
10	[0,0,0,0,0,0,0,0,3,4,3]	[1,1,1,1,1,1,1,1,0,0,2]

풀이

과녁은 10점 -> 0점 으로 순차적으로 쏜다.

1) 현재 남은 화살의 개수 >= 어피치가 K점 과녁에 쏜 화살의 개수 + 1

      (1) 어피치가 K점 과녁에 쏜 화살의 개수 + 1

      (2) 화살을 쏘지 않고 넘어가는 경우

     두 가지 경우가 존재한다.

2) 현재 남은 화살의 개수 <= 어피치가 K점 과녁에 쏜 화살의 개수

     남은 화살을 모두 쏴도 어피치가 점수를 가져가게 되므로, 쏘지 않고 넘어간다.

3) 0점 과녁

    남은 화살이 존재 할 경우 모두 쏴야한다.

 

dfs로 완전 탐색을 구현한다.

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

using namespace std;

vector<int> answer(1, -1);
int maxdiff = 0;

bool cmp(vector<int> ryan){
    for(int i = 10; i  >= 0; i--){
        if(ryan[i] > answer[i]){
            return true;
        }
        else if(ryan[i] < answer[i]){
            return false;
        }
    }
    return false;
}

void calScore(vector<int> ryan, vector<int> apeach){
    int ryanScore = 0, apeachScore = 0;

    for(int i = 0; i < 11; i++){
        if(ryan[i] > apeach[i]){
            ryanScore += ( 10 - i);
        }
        else if(apeach[i] > 0){
            apeachScore += ( 10 - i);
        }
    }
    int diff = ryanScore - apeachScore;
    if(diff > 0 && maxdiff <= diff){
        if(maxdiff == diff && !cmp(ryan))   return;
        maxdiff = diff;
        answer = ryan;
    }
}

void dfs(int idx, int arrows, vector<int> ryan, vector<int> apeach){
    if(idx == 11 || arrows == 0){
        ryan[10] += arrows;
        calScore(ryan, apeach);
        ryan[10] -= arrows;
        return;
    }
    if(apeach[idx] < arrows){
        ryan[idx] += apeach[idx] + 1;
        dfs(idx + 1, arrows - apeach[idx] - 1, ryan, apeach);
        ryan[idx] -= apeach[idx] + 1;
    }
    dfs(idx+1, arrows, ryan, apeach);
}

vector<int> solution(int n , vector<int> info){
    vector<int> ryan(11 , 0);
    dfs(0 , n, ryan, info);
    if(answer.empty()){
        answer.push_back(-1);
    }

    return answer;
}

int main(){

    vector<int> info = {2,1,1,1,0,0,0,0,0,0,0};
    int n = 5;

    vector<int> result = solution(n, info);
    
    for(const auto &it : result){
        cout << it << " ";
    }
    
    return 0;
}

 

    다른 방법

int GetScore(const vector<int>& Apeach, const vector<int>& Ryan) {
	int ret = 0;
	for (int i = 0; i <= 10; i++) {
		if (!Apeach[i] && !Ryan[i]) continue;
		if (Apeach[i] < Ryan[i]) ret += 10 - i;
		else ret -= 10 - i;
	}
	return ret;
}

vector<int> solution(int n, vector<int> Apeach) {
	vector<int> ret, Ryan(11); int mx = 0;
	auto DFS = [&](int pos, int arrows, auto&& DFS) -> void {
		if (pos == -1 && arrows) return;
		if (arrows == 0) {
			const auto res = GetScore(Apeach, Ryan);
			if (res > mx) mx = res, ret = Ryan;
			return;
		}
		for (int i = arrows; i >= 0; i--) {
			Ryan[pos] = i;
			DFS(pos - 1, arrows - i, DFS);
			Ryan[pos] = 0;
		}
	};
	DFS(10, n, DFS);
	return mx ? ret : vector<int>{ -1 };
}