Coding Test/programmers
[프로그래머스] 양궁대회 c++
owls
2022. 9. 26. 13:30
728x90
문제 설명
카카오배 양궁대회 결승전에 라이언과 어피치가 대결한다.
어피치가 먼저 화살을 모두 쏜 후, 라이언이 화살을 모두 쐈을 때, 라이언이 큰 점수 차이로 이기는 방법을 구하는 문제이다. (방법이 여러개라면, 가장 낮은 점수를 더 많이 맞히 경우가 정답이다.)
점수 계산법
- 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 };
}728x90