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

https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=java

프로그래머스

 

요구사항 분석

어피치의 결과가 주어짐.

한 점수를 더 많이 맞춰서 내 점수로 만들 수 있음.

어떻게 해도 라이언이 이길 수 없는 경우 -1을 return

라이언이 이기는 경우 똑같은 점수로 이긴다면, 가장 낮은 점수를 더 많이 맞힌 경우를 return

과녁은 0~10점, 화살의 갯수는 최악 10. 즉, 매우 낮은 시간 복잡도 = 완전 탐색

dp로도 시도 해 보았지만, 쉽지 않았음.

 

사고의 흐름

우선, 완전 탐색에서는 조합을 만들어서 탐색한다.

즉, 10점(index == 0)부터 시작해서 재귀를 통해 선택, 선택x인 재귀를 계속 호출해준다.

죠큼 까다로운 문제였다. 가장 낮은 점수를 더 많이 맞힌 경우 return에서 막힌 것 같다.

->완탐에서 사이즈가 명확한 조합은 for문 돌리는 게 더 쉬웠지만, 이 문제처럼, 사이즈가 명확하지 않은 조합은 선택x와 선택의 재귀를 돌리는게 더 쉬운 것 같다.

 

 

코드

import java.util.*;

class Solution {
    private int diff = 0;
    private int[] result = new int[11]; // 결과를 저장할 배열
    
    public int[] solution(int n, int[] info) {
        // 탐색을 시작할 때 크기 11인 배열을 사용
        search(n, info, 0, new int[11]);
        
        // 결과가 없으면 -1 반환
        if (diff == 0) {
            return new int[] {-1};
        }
        
        return result; // 결과 반환
    }
    
    public void search(int n, int[] info, int index, int[] arr) {
        if (index > 10 || n <= 0) {
            int apeach = 0;
            int lion = 0;
            for (int i = 0; i <= 10; i++) {
                if (info[i] == 0 && arr[i] == 0) continue;
                if (info[i] >= arr[i]) {
                    apeach += 10 - i;
                } else {
                    lion += 10 - i;
                }
            }
            if (lion > apeach && (lion - apeach >= diff)) {
                     if(n != 0){
                    arr[10] = n;
                }
                if(lion-apeach == diff){
                    for(int i = 10; i >= 0; i--){
                        if(result[i] == arr[i])continue;
                        if(result[i] < arr[i]){
                            diff = lion - apeach;
                            result = Arrays.copyOf(arr, arr.length);
                            return;
                        }else{
                            return;
                        }
                    }
                }
                diff = lion - apeach;
                result = Arrays.copyOf(arr, arr.length); // 결과 배열 복사
            }
            return;
        }
        
        search(n, info, index + 1, arr);    //그냥 넘어가던가

        if (n > info[index]) {  //선택 후 넘어가던가.
            arr[index] = info[index] + 1;
            search(n - (info[index] + 1), info, index + 1, arr);
            arr[index] = 0;
        }
    }
}