[양궁대회]

 

 

우선 아주 오랫동안 고민해보아도 스스로 풀 수 없을 것 같아 구글링을 했더니 풀이를 설명해주는 영상이 있어서 영상을 참고하여 이해를 해보기로 하였다. (아니.. 제한사항 저거를 어떻게 모두 만족하냐고요..)

(1) 비트형으로 표현된 부분집합의 원소값으로 모든 경우의 수를 구한다.
(2) 모든 경우의 수를 구한다 → '완전탐색'
(3) 쏘는 값을 계산해서 라이언과 어피치의 점수값을 계산해서 점수차이가 큰걸 maxDiff에 저장한다. 

이런 식으로 경우의 수를 돌면서 라이언이 이길 때마다 maxDiff에 저장시킨다. 이게 답이 될 수 있는 하나의 후보가 되는 것! 이렇게 돌면 첫번째 예제에서는 답이 maxDiff = 6으로 나온다!

그럼 이제 코드로 짜보자!

import java.util.*

class Solution {
    public int[] solution(int n, int[] info) {
        int[] answer = new int[11]; // 반환은 동일하게 11점
        int[] tmp = new int[11]; // 예시 후보
        int maxDiff = 0; // 가장 큰 값
        
        for(int subset = 1; subset < (1<<10); ++subset){ // 비트연산을 통해 구하기
        	int ryan = 0; apeach = 0; cnt = 0; // 몇개 사용했는지 카운팅 용도
            for(int i = 0; i<10; ++i){
            	if(( subset & 1 << i))!=0){ // i번째 비트만 1로 켜진다
            		// &는 둘 다 1인 경우 1 반환하고, 그렇지 않은 경우 0 반환
                    // <<는 비트를 왼쪽으로 n만큼 이동
                    // subset이라는 변수가 표현하는 부분집합에서 i번째 비트가 1인지 검사
                    // subset의 i번째 비트가 1인지 아닌지를 검사하는 조건문
                	ryan += 10 - i; // 라이언이 가져가는 점수
                    tmp[i] = info[i] + 1; // 라이언이 맞춘 화살개수는 어피치 +1
                    cnt += tmp[i]; // 라이언 사용 개수는 바로 위 tmp[i]인거
                } else {
                	tmp[i] = 0; // 라이언이 못이겼으면 안쏘면 되지
                    if(info[i] > 0) // 어피치가 이긴게 0보다 큰거면 
                    	apeach += 10 - i; // 이게 어피치가 가져가는 점수인거
                }
            }
            
        	if(cnt > n) continue; // 화살을 더 쓰게 되었으면 무시시켜야함
            
            tmp[10] = n - cnt; // 전체사용개수 - 지금사용개수 (0점개수기록)
            
            // maxDiff 보다 큰거 계산하기
            if(ryan - apeach == maxDiff){ // 둘이 점수가 같다면
            	for (int i = 10; i >= 0; --i){ // for문 돌려서 끝에서부터 하나하나 비교
                	if(tmp[i] > answer[i]{
                    	maxDiff = ryan - apeach;
                		answer = Arrays.copyOf(tmp, tmp.length);
                        break;
                    } else if (tmp[i] < anwer[i] {
						break;
                    }
                }
            } else if(ryan - apeach > maxDiff){ // 라이언이 이긴다면
            	maxDiff = ryan - apeach;
                answer = Arrays.copyOf(tmp, tmp.length); // tmp에 있는거 가져오기
            }
        }
        // 만약 라이언이 못이긴다고 하면 maxDiff가 0으로 남아있을테니까 분기처리하기
        if(maxDiff == 0){
        	return new int[]{-1); // 지면 -1 반환해야하니까
        }
        return answer;
    }
}

하나하나 디버깅을 해보며 주석을 달아보니까 이해가 잘 되었다!