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

1. 문제

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

프로그래머스

 

 

 

2. 풀이과정

1. 점수를 얻기 위한 최소 화살의 수를 계산하여 저장 + 남은 건 다 0에 넣는다.

- 같은 점수면 낮은 점수에 화살이 많은 것을 선택하기 때문에 개수가 딱 떨어지지 않으면 0으로 넣는다.

- 비트마스킹으로 낮은 점수에 화살이 많은 것을 구분한다.

2. dfs로 최대 점수를 계산한다.

- 어피치의 점수를 뺏은 경우 2배로 얻는다.

class Solution {
    int lion[][], max, result;
    //사용할 수 있는 화살 수, 맞힌 과녁, 점수합, 살펴본 점수
    public void dfs(int cnt, int selected, int sum, int now){
        if(cnt>=0 && max<=sum){
            if(max<sum || (max==sum && selected>result)){
                max = sum;
                result = selected;
            }
        }
        if(cnt==0){return;}
        for(int i=now; i<=10; i++){
            if(cnt-lion[i][0]<0){
                continue;
            }
            dfs(cnt-lion[i][0], selected | (1<<i), sum+lion[i][1], i+1);
        }
    }
    
    public int[] solution(int n, int[] info) {
        int[] answer = new int[11];
        int peach = 0;
        lion = new int[11][2];
        for(int i=0; i<=10; i++){
            lion[i][0] = info[i]+1;
            lion[i][1] = 10-i;
            if(lion[i][0]>1){
                peach += 10-i;
                lion[i][1]+=10-i;
            }
        }
        dfs(n, 0, 0, 0);
        if(max-peach<=0){
            return new int[]{-1};
        }
        int cnt = n;
        for(int i=0; i<=10; i++){
            if((result&(1<<i))!=0){
                answer[i] = lion[i][0];
                cnt-=answer[i];
            }
        }
        answer[10] += cnt;
        return answer;
    }
}