프로그래머스(카카오) | LV.2 양궁대회 - DFS, 완탐 문풀 (Java)

⬛ 프로그래머스(카카오) | LV.2 양궁대회 - DFS, 완탐 문풀 (Java)

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

프로그래머스

문제 설명 1

과녁판

문제 설명2

---

💚문제 접근 방식

• 문제 예시를 보면 n발을 어떤 조합으로 배치해서 어피치를 최대 점수 차로 이기는지, 그리고 그 조합이 여러 개라면 더 낮은 점수를 많이 맞힌 케이스로 리턴하라고 되어 있다.
• 처음에는 이거를 어떻게 컨트롤해서 n발을 배치하는 게 나은가 생각하다가 완전 탐색으로 결국 모든 케이스를 구해야 하는 문제구나 싶었다. 
• 결과적으로 DFS깊이를 n발 모두 사용할 때까지 갔다가 백트래킹해서, n발을 구성할 수 있는 모든 케이스를 탐색해보고, 그 중 최대 점수 차를 갖는 조합을 리턴하면 된다.
• 만약 DFS를 돌고도 max값이 -1이라면 이길 수 없다는 것이므로 -1 리턴한다.

💚 제출 코드

import java.util.*;

class Solution {
    private static int[] lion = {-1};
    private static int max = Integer.MIN_VALUE;
    private static int[] res = new int[11];//라이언이 쏜 화살 배열 
    //점수차 구하기 
    private static int score(int[] info){
        int apeach = 0, lion = 0;
        
        for(int i=0; i<res.length; i++){
            if(info[i]==0&&res[i]==0) continue;
            if(info[i]>=res[i]) apeach += (10-i);
            else lion += (10-i );
        }
        int diff = lion - apeach;
        if(diff<=0) return -1; //라이언<어피치
        return diff;
    }
    
    //DFS 백트래킹
    private static void DFS(int lv, int n, int[] info){
        //깊이 n까지 오면 
        if(lv == n){
            //계산해서 점수 차 
            int diff = score(info);
            if(max <= diff){
                max = diff;
                lion = res.clone();//복사
            }
            return;
        }
        for(int i=0; i<info.length && res[i] <= info[i]; i++){
            res[i]++;
            DFS(lv+1, n, info);
            res[i]--;
        }
        
    }
    
    //솔루션 함수 
    public int[] solution(int n, int[] info) {
        DFS(0, n, info);
        
        if(max == -1){//라이언이 어피치를 못 이길 경우
            lion = new int[1];
            lion[0] = -1;
        }
            
        return lion;
    }
}

💚 회고

특정한 규칙성이 없어서 모든 경우의 수를 따지는 백트래킹을 활용해야곘구나 생각은 했지만, 그 생각을 토대로 논리적으로 구현하는 게 힘들었다. 코드를 참고해서 해결했고, 시간 내에는 해결 못했다.. 연습이 더 필요할 듯 ㅠㅅㅠ