2022 Kakao blind 92342 - 양궁대회(백트래킹 or 그리디+완전탐색)) - Java 풀이

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

코딩테스트 연습 - 양궁대회

- 라이언이 어피치를 최대 점수로 이기는 양궁 점수 조합을 만들어야되는데, 최대점수 조합이 여러 개이면, 더 낮은 점수과녁을 많이 맞춘 조합을 리턴한다. 

- 이 문제를 풀면서 순열, 조합, 중복순열, 중복조합 공식과 코드 구현에 대해서 다시 한번 정리하였다. 

https://m.blog.naver.com/alwaysneoi/100186325649

 

- 처음에 이 문제를 보자마자 n의 값이 작아보여서 완전탐색으로 접근하였지만 시간초과가 발생했다. (중복순열 구현함)
아래 코드 복잡도는 O(M^N)이다
n값이 작은 테스트케이스 2개만 통과하였는데 n = 5 정도면 11^5 = 16만이지만 n= 10이면 11^10 = 259억 이므로 절대 통과할 수 없다

int[] lionInfo = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    
void go(int rest) {
        if(rest == 0) { // 계산해서 점수차가 더 크면 ans 대입, 만약 점수가 같으면 앞에서부터 비교, 계속 같다가, 작은 수가 나오면 ans대입
    		{.... 점수계산}
        }
        
        for(int i = 0; i < 11; ++i) {
            ++lionInfo[i];
            go(rest - 1);
            --lionInfo[i];
        }
}

- 복잡도를 줄여야하는데 만약 순서를 생각하지 않고 중복을 허용하는 중복조합 방식으로 로직을 구현하면 복잡도는 O(H(N, M)) = H(10, 11) = C(20, 11) =  16만이다. 라이언이 맞춘 과녁을 10점부터 0점까지 순서대로 확정하게 되면 결과적으로는 순서를 생각하지 않는 중복조합을 구현하는 것과 같다. 

void go(int idx, int rest, int[] info) {
	// idx가 과녁 끝까지 도달하면 남은 화살은 과녁 0점에 대입
    .. 점수계산
}

// main
for(int i = 0; i <= rest; ++i) {
   lionInfo[idx] = i;
   go(idx + 1, rest - i, info);
}

import java.util.*;

class Solution {
    int[] lionInfo = new int[11]; // 10~0
    int[] best = {-1};
    int bestscore = 0;
    
    public int[] solution(int n, int[] info) {
        go(0, n, info);
        return best;
    }
    
    void go(int idx, int rest, int[] info) {
        if(idx == 10) {
            lionInfo[10] = rest;
            
            int score = 0;
            for(int i = 0; i < 11; ++i) {
                if(lionInfo[i] > info[i]) score += (10 - i);
                else if(info[i] != 0) score -= (10 - i);
            }
            
            if(score <= 0) return;
            
            boolean ok = false;
            if(bestscore < score) ok = true;
            else if(bestscore == score) {
                for(int i = 10; i >= 0; --i) {
                    if(lionInfo[i] == best[i]) continue;
                    if(lionInfo[i] > best[i]) {
                        ok = true;
                        break;
                    } else break;
                }
            }
            
            if(ok) {
                bestscore = score;
                best = Arrays.copyOf(lionInfo, 11);
            }
            
            return;
        }
        
        for(int i = 0; i <= rest; ++i) {
            lionInfo[idx] = i;
            go(idx + 1, rest - i, info);
        }
    }
}

- 또는 라이언이 피치보다 많이 맞춰서 점수를 얻는 과녁을 미리 확정해서 점수를 계산하는 방식도 있다. 점수를 주는 과녁이 1점~10점 10개이므로 조합의 갯수가 2^10 = 1024이므로 비트마스킹 등을 이용해서 해당 조합에 대해서 가능한 조합을 그리디하게 접근할 수 있다. 

for(int i = 0; i < (1 << 10); ++i) {
	// 맞춘 과녁 0000000000~1111111111
	// 맞추지 않을 과녁은 0개, 맞춘 과녁은 피치보다 +1개, 나머지 화살은 모두 0점에 넣는 구현이 가능한지 검사
}