문제

기존 배열을 보고 이와 비교하며 최대값을 얻는 문제다.
링크

방향

array[11]에는 들어가는 값의 합은 n이 되어야해서
중복조합(맞나?) 경우의 수가 생긴다.

근데 문제를 잘 뜯어보면 점수를 얻기위해서는 info의 값보다 무조건 커야하므로 안넣으면 0 넣으면 info[i]+1 이 된다.

즉 결과값은 boolean result[11]이라고 봐도 된다.
그러면 총 2^11의 경우의수가 나온다.

그래서 2^11을 전체 순회하면 된다.

가장먼저 생각난 방법은 2가지 방향으로 트리를 순회하는 것이다.
문제는 순회하는 순서가 중요하다. 같은 결과값이라고해도 뒷숫자가 커야하는 조건이 있기때문이다.
그러면 큐를 써야하나 싶다가 두번째 방법이 떠올랐다.

두번째는 비트마스킹을 이용하는것이다.
2^11=2048을 2진수로 표현하면 10자리를 boolean으로 대체 생각할수있다.
1씩 더함으로써 방문 순서 문제도 해결되고
몇번째 배열을 사용하는지도 해결가능하다.
(대신 구현할때는 10110111 처럼 주석으로 써놔야 생각하기가 쉽다.)

CODE

class Solution4{
    // lion, peach
    private static int maxDiff=0,lionBit,lionArrowCnt;
    public int[] solution(int n, int[] peachArrows) {
        for(int bit=0;bit<(2<<11);bit++){
            int arrowCnt=getLionArrowCnt(bit,peachArrows);
            if(arrowCnt>n) continue;
            int lionScore=getLionScore(bit);
            int peachScore=getPeachScore(bit,peachArrows);
            int scoreDiff=lionScore-peachScore;
            if(scoreDiff>=maxDiff){
                maxDiff=scoreDiff;
                lionBit=bit;
                lionArrowCnt=arrowCnt;
            }
        }
        // make answer
        return getAnswer(n,peachArrows);
    }
    private int getLionArrowCnt(int bit,int[] peachArrows){
        int cnt=0;
        for(int i=0;i<11;i++){
            if((bit&(1<<i))!=0){
                cnt+=peachArrows[i]+1;
            }
        }
        return cnt;
    }
    private int getLionScore(int bit){
        int score=0;
        for(int i=0;i<11;i++){
            if((bit&(1<<i))!=0){
                score+=(10-i);
            }
        }
        return score;
    }
    private int getPeachScore(int bit,int[] peachArrows){
        int score=0;
        for(int i=0;i<11;i++){
            if((bit&(1<<i))==0 && peachArrows[i]!=0){
                score+=(10-i);
            }
        }
        return score;
    }
    private int[] getAnswer(int n,int[] peachArrows){
        int[] ans;
        if(0>=maxDiff) {
            ans=new int[1];
            ans[0]=-1;
        }
        else{
            ans=new int[11];
            for(int i=0;i<11;i++){
                if((lionBit&(1<<i))!=0) ans[i]=peachArrows[i]+1;
            }
            int remain=n-lionArrowCnt;
            ans[10]+=remain;
        }
        return ans;
    }
}
public class P4 {
    public static void main(String[] args){
        Solution4 sol = new Solution4();
        int n=5;
        int[] info={2,1,1,1,0,0,0,0,0,0,0};
        int[] ans=sol.solution(n,info);
        for(int a:ans) System.out.print(a+" ");
        
    }
}