프로그래머스 양궁대회 python, java

재귀함수를 통한 모든 경우의 수를 확인하여 풀었다.
과녁이 10점까지였기에 별도의 백트래킹은 하지 않았다.

자바로 푸는 과정에서 함수인자로 배열이 들어가게 되면 파이썬과 다르게 1차원 배열임에도 깊은복사 처리를 해줘야했다. 이 때문에 arr을 solution내에서 정의할 필요가 없어져 static 변수로 빼주고 처리했다.

📜 문제 바로 가기 : 양궁대회

제출코드

파이썬

def solution(n, info):
    
    # 큰 점수차로 이기기 위해 과녁에 맞출 화살의 개수는 0개 or k개 이다.
    
    # s: 남은 화살, a: 내점수, b: 상대점수, idx: 점수 인덱스
    # arr: 정보배열
    def solve(s=n, a=0, b=0, idx=0, arr = []):
        nonlocal point, answer      
    
        if len(arr) == 11:
                
            if point < a-b:
                point = a-b
                answer = arr
            elif point == a-b:
                for i in range(10, -1, -1):
                    if answer[i] < arr[i]:
                        answer = arr
                        break
                    elif answer[i] > arr[i]:
                        break
                
            return
        
        p = 10 - idx
        if p == 0:
            solve(0, a, b, idx+1, arr+[s])
            return
        
        arrow_B = info[idx]
        # 1. 내가 점수를 가져가는 경우
        if arrow_B +1 <= s:
            solve(s-(arrow_B+1), a+p, b, idx+1, arr+[arrow_B +1])
        
        # 2. 이 점수를 포기하는 경우
        if arrow_B != 0 :
            solve(s, a, b+p, idx+1, arr+[0])
        else:
            solve(s, a, b, idx+1, arr+[0])
        
    point = -1 # 점수차
    answer = [0,0,0,0,0,0,0,0,0,0,0]
    solve()
    
    if point <= 0:
        answer = [-1]
    

    return answer

자바

class Solution {
    static int[] infoArr;
    static int point = -1;
    static int[] answer = {0,0,0,0,0,0,0,0,0,0,0};
    static int[] arr = {0,0,0,0,0,0,0,0,0,0,0};
    
    public int[] solution(int n, int[] info) {
        infoArr = info;
        solve(n, 0, 0, 0);
        
        if (point <= 0) {
            answer = new int[]{-1};
        }
        
        return answer;
    }
    
    public void solve(int s, int a, int b, int idx) {
        if (idx == 11) {
            
            if (point < a-b) {
                point = a-b;
                answer = arr.clone();
                
            } else if (point == a-b) {
                for (int i = 10; i >= 0; i--) {
                    if (arr[i] > answer[i]) {
                        answer = arr.clone();
                        break;
                    } else if (arr[i] < answer[i]) {
                        break;
                    }
                }
            }
            return ;

        }
        
        int p = 10 - idx;
        int arrow_B = infoArr[idx];
        if (p == 0) {
            arr[idx] = s;
            solve(0, a, b, idx+1);
            arr[idx] = 0;
            return ;
        }
        
        if (s >= arrow_B+1) {
            arr[idx] = arrow_B+1;
            solve(s-(arrow_B+1), a+p, b, idx+1);
            arr[idx] = 0;
        }
        
        if (arrow_B != 0) {
            solve(s, a, b+p, idx+1);
        } else {
            solve(s, a, b, idx+1);
        }   
    }
}

---

접근 방법

어피치에게 유리한 룰이 적용되어 맞힌 화살의 개수가 같더라도 점수는 어피치가 획득한다.
그렇다면 최대 점수를 얻기위해 라이언이 해야될 조치는 딱 1개 차이로 앞서 점수를 얻거나 아예 포기하여 다음 과녁을 노리는 것이다.