라이언을 억까하는 양궁대회이다.
우선 처음에 그리디 알고리즘으로 풀어보려 했다. 쏜 화살 갯수 대비 가장 효율이 좋은, (획득점수/쏴야되는화살갯수)가 높은 순으로 쏜 결과를 구하려 했는데, 생각해보니 해당 과녁에 점수를 쏘았을 때, 어피치가 점수를 획득하냐 라이언이 점수를 획득하냐에 따른 우선순위를 고려할 수 없었다. 따라서 중복조합 으로 풀어야 한다. 과녁도 10칸이고 화살은 10개 이하로 쏘기 때문에 시간초과가 나지 않는다.
11개짜리 배열을 만들어서, 총 화살 갯수를 분배하는 중복 조합을 탐색한다.
만들어진 중복조합 중 라이언과 어피치의 점수차가 가장 큰 경우, 점수차가 같은 조합이 두개 이상이라면 낮은 화살에 많이 맞은 경우를 찾는다.
만들어진 중복조합에서 라이언이 어피치를 이길 수 없다면 [-1] 을 리턴한다.
/*
조건)
라이언은 불리하게 게임 함
더 많은 화살을 k 점에 맞힌 선수가 k 점을 획득
두 선수가 같은 점수의 과녁에 같은 발을 맞췄다면 어피치가 이김
둘다 k 점에 맞히지 못한 경우 둘 다 0점
결과 판별)
최종 점수를 비교, 어피치>=라이언 일 경우 어피치가 우승
목표)
라이언이 가장 큰 점수차로 이기기 위해 n 발의 화살을 각각 어느 과녁 점수에 맞혀야 하는지 구하기
[10점,9점,8점,7점,6점,5점,4점,3점,2점,1점,0점] 순으로 리턴
가장 큰 점수차가 나오는 방법이 여러 가지 인 경우 가장 낮은 점수를 더 많이 맞힌 경우로 리턴
라이언이 우승할 수 없는 경우 [-1]
*/
/*
Sol1) 그리디 -> 화살 개수 대비 가장 점수를 많이 획득하는 순으로 쏘기
- > 반례가 있음. (2발 쏴서 얻는 점수 < 1발씩 두번 쏘는 점수 인 경우)
Sol2) 모든 중복조합으로 조회
과녁의 점수는 11가지, 화살의 갯수는 10 이하이므로 시간초과 나지 않음
*/
import java.util.*;
class Solution {
static ArrayList<int[]> shoots = new ArrayList<>();
public int[] solution(int n, int[] info) {
dfs(0, n, 0, new int[11]);
int[] answer = new int[11];
int max=0;
for(int[] ryan : shoots){ // 라이언의 정보
int ryanPoint = 0;
int apeachPoint = 0;
for(int i=0;i<11;i++){
// 둘 다 맞히지 못한 과녁 = 둘 다 0점
if(ryan[i]==0 && info[i]==0){
continue;
}
// 과녁의 점수에서 라이언이 더 많이 맞췄다면
if(info[i]<ryan[i]){
ryanPoint+=10-i;
}
// 과녁의 점수에서 어피치가 더 많거나 같게 맞췄다면
else{
apeachPoint+=10-i;
}
}
int diff = ryanPoint-apeachPoint; // 해당 조합에서 라이언과 어피치의 점수차이
if(diff<=0){
continue;
}
if(max<diff){
max=diff;
answer=ryan.clone();
}
if(max==diff){ // ryan = 새로 들어온 조합, answer = 기존 조합
for(int i=10;i>=0;i--){
if(ryan[i]>answer[i]){
answer=ryan.clone();
break;
}
else if(ryan[i]==answer[i]){
continue;
}
else{
break;
}
}
}
}
// max 가 0 인 경우(라이언이 지거나 비기는 경우만 있음)
if(max==0){
return new int[]{-1};
}
return answer;
}
// 모든 중복 조합을 추가해주는 메소드
public static void dfs(int shot, int n, int index, int[] result){
if(shot == n){
// 깊은 복사로 static arraylist에 추가
int[] data = result.clone();
shoots.add(data);
return;
}
// 현재 인덱스에 몇개의 화살을 쏠 것인지
for(int i = 0 ; i <= n ; i++){
if(index==result.length){
return;
}
if(shot>n){
return;
}
// 해당 인덱스에 i 개를 쏨
int prev = result[index];
result[index]=i;
dfs(shot+i,n,index+1,result);
result[index]=prev;
}
}
}