[프로그래머스] 양궁대회 (JAVA)

문제 풀러가기

문제 분석

문제를 읽자마자 떠오른 방법은
완전탐색!
다 돌려봐야 한다

DFS를 돌려서 문제 예시를 파악해서 3가지의 조건을 처리 해줬는데, 자꾸 틀렸음..
알고보니,

라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.

이런 조건이 있었음... 주의하자. 문제를 잘 읽자 ㅠㅠ


그리고 이후에도 계속 테케를 하나만 못맞췄는데,
3번을 맞추면 4번이 틀리고, 4번을 맞추면 3번이 틀리고 했었다

알고보니까

라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.

이 조건을 처리할 때, 점수 비교 시 같은 게 아닌 이상 한쪽이라도 더 큰 곳이 있었다면 바로 return 처리를 해줘야 하는 것

이 부분을 놓쳐서 계속 바뀌는 문제가 발생했었다

---

풀이 방법

문제 예시에서 파악할 수 있는 경우의 수 3가지

둘다 0으로 점수 받기 포기, 어피치 이기기, 어피치한테 지기

어피치한테 지기는 0점부터 ~ 어피치보다 1점 낮게까지 다 돌려줘야 함

3개의 경우의 수를 DFS (부분집합) 코드를 돌리면 된다

돌리고 점수 계산 후 정답 계산!

---

내 코드

import java.util.*;

class Solution {
    static int N, maxMinus;
    static int[] arr;
    static int[] answer = {-1};
    public int[] solution(int n, int[] info) {
        N = n;
        maxMinus = -1;
        arr = new int[11];
        dfs(info, 0, 0);

        return answer;
    }
    
    //idx는 점수 0~10까지 접근, cnt는 사용한 화살 수
    private static void dfs(int[] apeach, int idx, int cnt) {
        if(idx == 11) { //점수 접근을 다 했으면
            //화살 다 썼는지 확인하고 다 썼으면 점수 계산
            if(cnt == N) {
                int apScore = 0, liScore = 0;
                for(int i = 0; i<11; i++) {
                    if(apeach[i] == 0 && arr[i] == 0) {
                        continue;
                    }
                    if(apeach[i]>=arr[i]) apScore += 10-i;
                    else liScore += 10-i;
                }
                
                if(liScore>apScore) {
                    //라이언이 가장 큰 차이로 이기는 경우
                    if(liScore-apScore > maxMinus) {
                        maxMinus = liScore-apScore;
                        answer = arr.clone();
                    }
                    //라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우
                    else if(liScore-apScore == maxMinus) {
                        for(int i = 10; i>=0; i--) {
                            if(answer[i]<arr[i]) {
                                answer = arr.clone();
                                return;
                            }
                            else if(answer[i]>arr[i]) return;
                        }
                    }
                }
            }
            return;
        }
        
        //둘다 0으로 점수 받기 포기
        if(apeach[idx] == 0) {
            dfs(apeach, idx+1, cnt);
        }
        
        //어피치 이기기
        if(cnt+1+apeach[idx] <= N) { //현재까지 사용한 화살 수+1에 어피치 화살 수를 더해도 전체 화살 수가 넘지 않으면
            arr[idx] = apeach[idx]+1;
            dfs(apeach, idx+1, cnt+1+apeach[idx]);
            arr[idx] = 0;
        }
        
        //어피치한테 지기
        if(apeach[idx] != 0) {
            for(int i = 0; i<=apeach[idx]; i++) {
                arr[idx] = i;
                dfs(apeach, idx+1, cnt+i);
                arr[idx] = 0;
            }
        }
        
    }
}

앞으로 문제를 잘 읽고, return을 잘 생각해서 사용하도록 하자