[Programmers] 양궁 대회 (Java)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

문제 풀이

라이언이 최대 점수차로 어피치를 이길 수 있는 과녁을 구한다.

과녁이 10개밖에 없기 때문에 가장 먼저 든 생각은 10번 반복문을 돌면서 점수를 먹는 경우, 안먹는 경우가 떠올랐다. 예제 1번을 예시로 들면 [2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 0번 Index의 10점을 얻으려면 3개의 화살이 필요하므로 cnt+3과 10점을 안먹는 경우 cnt를 그대로 넘기면서 하나의 Index 당 dfs를 2번 돌리면서 진행하며 남는 화살은 전부 0점 과녁인 10번 Index에 추가한다. 

화살을 모두 사용했거나 마지막 Index까지 간 경우 maxScore를 최대값으로 갱신하고 현재 score상태를 clone()함수를 통해 ans배열에 저장한 후에 ans배열이 전부 0이면 최대값이 갱신되지 않은 경우이므로 {-1}을 return하고 아니라면 ans배열을 return한다.

 

※ 고려해야 할점

1. 최대 점수차가 여러 경우일 경우 가장 낮은 점수를 더 많이 맞힌 경우 return
   최대 점수차가 같은 경우가 많을 수도 있기 때문에 시간 단축을 위해 0번 Index부터 시작하지 않고 끝 Index부터 시작하여 마지막으로 갱신된 값이 가장 낮은 점수를 많이 맞힌 경우가 되므로 따로 검사하지 않을 수 있었습니다.
2. 점수 구하기
   과녁을 모두 사용했을 경우 라이언과 어피치의 점수를 모두 구하는 것보다 라이언의 점수만 구하고 마지막에 어피치 점수와 비교하는 방식으로 조건문을 줄일 수 있었습니다. 이 방식을 사용하기 위해선 dfs를 시작하기 전에 점수판 board[11] 배열을 만든 후 어피치가 점수를 얻은 과녁판은 *2를 해준다. 이러면 어피치의 점수를 다시 계산하지 않고 라이언의 점수를 board[] 배열을 기준으로 구하고 마지막에 비교만 해준다면 코드와 시간을 줄일 수 있었습니다.
3. 라이언이 우승할 방법이 없는 경우 {-1} return 
   위와 같이 점수를 구한 후 마지막에 라이언의 점수가 어피치의 점수보다 같거나 작다면 -1을 return하고 아니라면 ans배열을 return한다면 조건에 맞는 과녁을 구할 수 있습니다.

코드

import java.util.*;
class Solution {
    public int[] solution(int n, int[] info) {
        
        // init
        int apeachScore = 0;
        for(int i=0; i<11; i++) {
            if(info[i] > 0) {
                apeachScore += (10-i);
                board[i] = (10-i) * 2;
            } else {
                board[i] = (10-i);
            }
        }
        
        dfs(n, 10, 0, info);
        
        if(maxScore > apeachScore){
            return ans;
        }
        
        return new int[] {-1};
    }
    
    int[] ans = new int[11];
    int[] score = new int[11];
    int[] board = new int[11];
    int maxScore = 0;
    public void dfs(int n, int now, int cnt, int[] info) {
        if(cnt == n || now == -1) {
            int nowScore = getScore();
            
            if(nowScore >= maxScore) {
                maxScore = nowScore;
                ans = score.clone();
                ans[10] += (n-cnt);
            }
            
            return;
        }
        
        dfs(n, now - 1, cnt, info);
        
        if(cnt + info[now] + 1 <= n) {
            int ryanScore = info[now] + 1;
            score[now] = ryanScore;
            dfs(n, now - 1, cnt+ryanScore, info);
            score[now] = 0;
        }
    }
    
    public int getScore() {
        int ryanScore = 0;
        
        for(int i=10; i>=0; i--) {
            if(score[i] > 0) {
                ryanScore += board[i];    
            }   
        }
        
        return ryanScore;
    }
    
}