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

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• DFS (백트래킹)

필요 자료구조
- 1차원 int형 정답 배열 lion
- 점수 차이가 최대일 때 라이언이 쏜 화살 수를 저장하는 1차원 int형 배열 arrows

 

백트래킹으로 n개를 뽑는 조합을 생성해 화살을 어디에 얼마나 맞추는지 구할 수 있다.

 

그런데 이 때 n = 10일 때 시간초과가 나므로, 백트래킹 메서드의 반복문에 가지치기(특정 조건 추가)해줘야 한다!

여기서 특정 조건은 과녁 i에 라이언이 임의의 점수에서 어피치에게 점수를 따내기 전까지 (arrows[i] <= info[i]) 만 반복문이 작동하게 하는 것!!(= 라이언이 어피치를 이기기 위해 최소 어피치가 쏜 화살 수만큼은 쏘기 위해 재귀를 진행한다. 이미 과녁을 많이 맞췄는데 더 많이 쏴봤자 의미 없고 시간 초과가 발생하기 때문)

 for(int i = 0 ; i < info.length && arrows[i] <= info[i] ; i++) {
    arrows[i]++;
    dfs(depth + 1);
    arrows[i]--;
}

 

 

그렇게 n개의 화살을 모두 다 할당했을 때, 라이언과 어피치의 점수 차이를 계산한다. 그리고 여태껏 점수 차의 최댓값과 비교해 더 크다면, 최댓값을 갱신하고, 정답 배열에는 arrows 배열의 내용을 복사한다. (clone)

 

만약 점수 차를 구했을 때 라이언의 점수가 어피치 점수보다 작거나 같다면, 어피치가 이긴 것이므로 -1을 출력하고 종료하게 한다.

 

 

 

💥 유의사항

n=10일 때 시간초과 발생하므로, 특정 조건을 미리 추가해 시간 초과를 방지하는 것이 포인트..!

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int n;
    static int[] info;
    
    static int[] lion = {-1};    // 정답 배열
    static int[] arrows = new int[11];  // 점수 차가 최대일 때 라이언이 쏜 화살 배열
    
    static int max = Integer.MIN_VALUE; // 최댓값
    
    public int[] solution(int n, int[] info) {
        this.n = n;
        this.info = info;
        
        dfs(0);
        
        if(max == -1) {
            lion = new int[]{-1};
        }
        return lion;
    }
    
    // 라이언이 쏜 화살에 대한 조합 구하는 메서드
    private static void dfs(int depth) {
        if(depth == n) {
            int diff = getScore();  // 점수 차 구하기
            
            if(max <= diff) {   // 🔔 점수 차 최댓값 갱신
                max = diff;
                lion = arrows.clone();
            }
            return;
        }
        
        // 🔔 arrows[i] <= info[i] : 과녁 i에 어피치가 화살을 더 많이 쏘는 경우
        for(int i = 0 ; i < info.length && arrows[i] <= info[i] ; i++) {
            arrows[i]++;
            dfs(depth + 1);
            arrows[i]--;
        }
    }
    
    // 점수 차 계산 메서드
    private static int getScore() {
        int apeach = 0;
        int lion = 0;
        
        for(int i = 0 ; i <= 10 ; i++) {
            if(info[i] == 0 && arrows[i] == 0)  continue;   // 어피치, 라이언 둘 다 0 맞추면 무시
            
            if(info[i] >= arrows[i])
                apeach += (10 - i);
            else
                lion += (10 - i);
        }
        
        int diff = lion - apeach;
        
        if(diff <= 0)
            return -1;
        return diff;
    }
}

 

 

 

➕ 다른 풀이 방식

dfs 부분이 좀 다르셔서 참고용

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

 

---

💦 어려웠던 점

- DFS인 건 캐치했는데 저 가지치기 조건을 생각하지 못 했다.ㅠ

- '라이언이 가장 큰 점수 차이로 우승할 수 잇는 방법이 여러 가지일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.' ⇒ 백트래킹을 앞 원소부터 순차적으로 진행하면서 차례대로 요소가 늘어나므로, 마지막에 나오는 최댓값이 낮은 점수를 가장 많이 맞힌 경우가 된다고 한다... (참고)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[JAVA] 프로그래머스 - 양궁대회 - lv2

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

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