[프로그래머스] 양궁대회 - Java

양궁대회(Lv2)

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

프로그래머스

 

 

 

 

풀이

이번 문제는 dfs(유사 부분집합)를 이용해 모든 경우의 수를 계산했다.
단, 몇개를 사용해서 이기던 점수는 한 번만 오르는 것에 유의해서 풀었다.

먼저 dfs의 파라미터는

1. idx : 현재 인덱스
2. remain : 남은 화살
3. int[] info : 어피치 정보
4. int[] compare : 라이언 정보

로 구성했다.

 

다음으로 dfs의 주요 로직은

1. info[idx](해당 인덱스에서 어피치가 맞힌 화살 갯수) >= remain인 경우에는 라이언이 화살을 다 써도 어피치를 이기지 못하므로 idx만 하나 늘려서 뒤로 넘겼다.
2. info[idx] < remain인 경우b. 해당 점수를 얻지 않고 인덱스를 늘린다.
3. a. 해당 점수를 얻고 인덱스를 늘린다
4. idx==11(끝에 도달) 이거나 remain <=0(화살을 모두 소모)인 경우 점수를 비교했다.b. 라이언이 어피치를 이길 수 있는경우, 기존 값(max)보다 더 크면 바로 answer를 갱신했다. 만약 max와 같다면 answer 배열의 뒤에서부터 비교해서 현재의 값이 더 큰 구간이 나오면 갱신하고, answer 배열의 값이 더 큰게 먼저 나오면 그대로 종료했다.
5. c. a에서 더했던 remain을 다시 빼준다.
6. a. remain이 남은 경우, 마지막에 더했다.(가장 낮은 점수가 많은 것이 우선순위기 때문)

 

 

전체 Code

import java.util.*;
class Solution {
    int max;
    int[] answer;
    public int[] solution(int n, int[] info) {
        max=0;
        int[] compare = new int[11];
        dfs(0,n,info,compare);
        if(max==0) return new int[]{-1};
        return answer;
    }
    
    private void dfs(int idx, int remain, int[] info, int[] compare){
        if(remain<0) return;
        if(idx==11 || remain<=0){
        	// 남은 친구들 마지막에 더해주기
            if(idx==11) {
                compare[10]+=remain;
            }else{
                
            }
            int lionScore = calculate(compare,info);
            
            if(lionScore>0){
   				// 최대값 갱신
                if(lionScore>max){
                    max = lionScore;
                    answer = compare.clone();
                } 
                // 같은 경우 뒤부터 비교
                else if(lionScore==max){
                    if (answer == null) {
                        answer = compare.clone();
                    } else {
                        for (int i = 10; i >= 0; i--) {
                            if (compare[i] > answer[i]) {
                                answer = compare.clone();
                                break;
                            }else if(compare[i] < answer[i]) break;
                        }
                    }
                }
            }
            // 더했던 친구들 다시 빼주기
            compare[10]-=remain;
            return;
        }
        // 남은만큼 다 써도 못이기는 경우 바로 넘기기
        if(info[idx]>=remain){
            dfs(idx+1, remain, info, compare);
        }
        // 이길 수 있으면  
        else{
            compare[idx] = info[idx]+1;
            // 1.써서 넘기기
            dfs(idx+1, remain-compare[idx], info, compare);
            compare[idx] = 0;
            // 2.안쓰고 넘기기
            dfs(idx+1, remain, info, compare);
        }
    }
    
    // 점수 비교
    private int calculate(int[] arr1, int[] arr2){
        int cnt=0;
        for(int i=0; i<11; i++){
            if(arr1[i]==0 && arr2[i]==0) continue;
            if(arr1[i]>arr2[i])
                cnt+=10-i;
            else cnt-=10-i;
        }
        return cnt;
    }
}