92342. 양궁대회

문제

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

제한사항 

풀이

class Solution {
    int[] answer = {-1};
    int maxDiff = 0;
    
    public int[] solution(int n, int[] info) {
        
        
        dfs(n, 0, new int[11], info);
        
        
        return answer;
    }
    
    
    void dfs(int n, int idx, int[] ryan, int[] apeach) {
        
        
        if(idx == 11) {
            if(n > 0) ryan[10] +=n;
            int ryanScore = 0;
            int apeachScore = 0;
            
            for(int i = 0 ; i < 11; i++) {
                if(ryan[i] == 0 && apeach[i] == 0) continue;
                if(ryan[i] > apeach[i]) ryanScore+=10-i;
                else apeachScore+=10-i;
            }
            
            if(ryanScore > apeachScore) {
                int diff = ryanScore - apeachScore;
                if(diff > maxDiff) {
                    answer = ryan.clone();
                    maxDiff = diff;
                } else if(diff == maxDiff) {
                    for(int i = 10 ; i >=0 ; i-- ) {
                        if(ryan[i] > answer[i]) {
                            answer = ryan.clone(); 
                            break;
                        } else if(ryan[i] < answer[i])
                            break;
                    }
                }
            }
            
            if(n > 0) ryan[10]-=n;
            return; 
        }
        
        
        // 라이언이 이기는 경우
        if(n > apeach[idx]) {
            ryan[idx] = apeach[idx] + 1;
            dfs(n - (apeach[idx]+1), idx+1, ryan, apeach);
            ryan[idx] = 0; // 백트래킹
        }
        
        // 라이언이 지는 경우
        dfs(n, idx+1, ryan, apeach);
            
    }
}

회고

백트래킹으로 풀어야겠다고는 생각했는데 구현이 쉽지 않았다. 구현 과정에서 잔실수가 많았다. 

 

k 점수에 대해서 라이언이 이기려면 어피치보다 과녁을 많이 맞춰야 한다. 맞춘 과녁이 서로 같아도 어피가 이긴다. 따라서, 백트래킹 과정에서 경우의 수를 나눌 때, 어피치가 이기는 경우와 지는 경우를 고려했다. 

// 라이언이 이기는 경우
        if(n > apeach[idx]) {
            ryan[idx] = apeach[idx] + 1;
            dfs(n - (apeach[idx]+1), idx+1, ryan, apeach);
            ryan[idx] = 0; // 백트래킹
        }
        
        // 라이언이 지는 경우
        dfs(n, idx+1, ryan, apeach);

 

dfs 종료 조건인 `idx == 1 `이 될 때 탐색을 마친다. 라이언에게 주어진 화살이 남을 경우가 존재할 수 있다. 그럴 경우 0점 과녁(idx = 10)에 남은 화살을 모두 몰아준다. 하지만 이 부분에서 실수를 했다. `ryan[10] = n`으로 작성하여 기존에 쏜 화살 개수를 덮어쓰는 문제가 있었다. 

if(idx == 11) {
            if(n > 0) ryan[10] +=n;
            int ryanScore = 0;
            int apeachScore = 0;
            
            for(int i = 0 ; i < 11; i++) {
                if(ryan[i] == 0 && apeach[i] == 0) continue;
                if(ryan[i] > apeach[i]) ryanScore+=10-i;
                else apeachScore+=10-i;
            }