[JAVA] 프로그래머스 level2 양궁대회

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

프로그래머스

코딩테스트 연습 > 2022 KAKAO TECH INTERNSHIP  > 양궁대회

 

문제 접근

백트래킹(재귀)문제!!

 

핵심정리

1. 어피치가 10점을 2발 맞혔고 라이언도 10점을 2발 맞혔을 경우 어피치가 10점

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

3. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정

4. 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return

5. 라이언이 어떻게 화살을 쏘든 라이언의 점수가 어피치의 점수보다 낮거나 같으면 [-1]을 return

 

나는 2가지 방법을 사용해서 문제를 풀었다.

1. 일반적인 백트래킹 + 가장 낮은 점수를 더 맞힌 경우를 구하는 로직 추가 

2. 일반적인 백트래킹의 순서를 바꾸기 

 

정답(전체) 코드1 - 가장 낮은 점수를 더 맞힌 경우를 구하는 로직 추가 

import java.util.*;
class Solution {
    static int [] infor;
    static boolean win = false; // 라이언이 이기는 경우가 있는 경우 true
    static int [] memo;   // 백트래킹용 배열 
    static int [] answer; // 정답 return 
    static int max;
    public int[] solution(int n, int[] info) {
        
        // 매개변수 -> static 
        infor = Arrays.copyOf(info, 11);
        
        memo   = new int [11];
        answer = new int [11];
        bt(0, 0, n, 0); // 우승 방법이 여러 가지 일 경우 가장 낮은 점수 많이 
        
        if(win) return answer;
        
        return new int [] {-1};
    }
    // 백트래킹 sc1:라이언 sc2: 어피치 n: 화살개수 depth: 점수 
    public static void bt(int sc1, int sc2, int n, int depth){
        if(depth == 11){
            if(n == 0 && sc1 - sc2 > max){
                win = true;
                max = sc1 - sc2;
                answer = Arrays.copyOf(memo, 11);
            }
            else if(n == 0 && sc1 - sc2 == max){ // 검증 로직 추가 
                boolean flag = true;
                for(int i = 10; i >= 0; i--){
                    if(answer[i] == memo[i]){
                       continue;
                    }
                    if(answer[i] > memo[i]) flag = false;    
                    break;    
                }
                if(flag) answer = Arrays.copyOf(memo, 11);
            }
            return;
        }
        
        for(int i = 0; i <= n; i++){ // 낮은 점수를 가장 많이 
            if(i == 0){
                if(infor[depth] == 0){
                    bt(sc1, sc2, n, depth + 1);
                }
                else{
                    bt(sc1, sc2 + 10 - depth, n, depth + 1);
                }
            }
            else{
                if(infor[depth] >= i){ // 어피치가 점수 획득 
                    memo[depth] = i;
                    bt(sc1, sc2 + 10 - depth, n - i, depth + 1);
                    memo[depth] = 0;
                }
                else{
                    memo[depth] = i;
                    bt(sc1 + 10 - depth, sc2, n - i, depth + 1);
                    memo[depth] = 0;
                }
            }
        }
    }
}

정답(전체) 코드2 - 일반적인 백트래킹의 순서를 바꾸기 

import java.util.*;
class Solution {
    static int [] infor;
    static boolean win = false; // 라이언이 이기는 경우가 있는 경우 true
    static int [] memo;   // 백트래킹용 배열 
    static int [] answer; // 정답 return 
    static int max;
    public int[] solution(int n, int[] info) {
        
        // 매개변수 -> static 
        infor = Arrays.copyOf(info, 11);
        
        memo   = new int [11];
        answer = new int [11];
        bt(0, 0, n, 10); // 우승 방법이 여러 가지 일 경우 가장 낮은 점수 많이 
        
        if(win) return answer;
        
        return new int [] {-1};
    }
    // 백트래킹 sc1:라이언 sc2: 어피치 n: 화살개수 depth: 점수 
    public static void bt(int sc1, int sc2, int n, int depth){
        if(depth == -1){
            if(n == 0 && sc1 - sc2 > max){
                win = true;
                max = sc1 - sc2;
                answer = Arrays.copyOf(memo, 11);
            }
            return;
        }
        
        for(int i = n; i >= 0; i--){ // 낮은 점수를 가장 많이 
            if(i == 0){
                if(infor[depth] == 0){
                    bt(sc1, sc2, n, depth - 1);
                }
                else{
                    bt(sc1, sc2 + 10 - depth, n, depth - 1);
                }
            }
            else{
                if(infor[depth] >= i){ // 어피치가 점수 획득 
                    memo[depth] = i;
                    bt(sc1, sc2 + 10 - depth, n - i, depth - 1);
                    memo[depth] = 0;
                }
                else{
                    memo[depth] = i;
                    bt(sc1 + 10 - depth, sc2, n - i, depth - 1);
                    memo[depth] = 0;
                }
            }
        }
    }
}