문제 링크

문제 간단 해석

상대보다 많은 화살을 맞히며, 점수를 빼앗아오는 문제.

Java

어피치의 점수를 class 내에 선언하여 계산하는 방식으로 풀었다. 재귀함수로 넘기는 게 더 깔끔한 코드가 나왔을 것 같다.

풀이 코드

class Solution {
    private int[] info;
    private int[] log = new int[11];
    private int[] bestLog = new int[11];
    private int bestScore = 0;
    private int enemyScore = 0;
    
    public void getScore(int score, int arrow, int step) {
        if (step == 10) {
            log[10] = arrow;
            
            if (score - enemyScore < bestScore)
                return;
            
            if (score - enemyScore > bestScore) {
                bestScore = score - enemyScore;
                bestLog = log.clone();
                return;
            }
            
            for (int i = 10; i >= 0; i--) {
                if (log[i] == bestLog[i])
                    continue;
                else if (log[i] > bestLog[i])
                    bestLog = log.clone();
                return;
            }
        }
        
        if (arrow > info[step]) {
            log[step] = info[step] + 1;
            enemyScore -= info[step] > 0 ? 10 - step : 0;
            
            getScore(score + 10 - step, arrow - info[step] - 1, step + 1);
            
            log[step] = 0;
            enemyScore += info[step] > 0 ? 10 - step : 0;
        }
        
        getScore(score, arrow, step + 1);
    }
    
    public int[] solution(int n, int[] info) {
        this.info = info;
        
        for (int i = 0; i < 10; i++)
            if (info[i] > 0)
                enemyScore += 10 - i;
        
        getScore(0, n, 0);
        
        return bestScore > 0 ? bestLog : new int[] {-1};
    }
}

해석

this.info = info;

for (int i = 0; i < 10; i++)
    if (info[i] > 0)
        enemyScore += 10 - i;

getScore(0, n, 0);

return bestScore > 0 ? bestLog : new int[] {-1};

어피치의 점수를 미리 계산, getScore 재귀함수를 돌리고 bestScore가 존재한다면 bestLog 배열을, 아니라면 [-1]을 반환하도록 했다.

...

if (arrow > info[step]) {
    log[step] = info[step] + 1;
    enemyScore -= info[step] > 0 ? 10 - step : 0;
    
    getScore(score + 10 - step, arrow - info[step] - 1, step + 1);
    
    log[step] = 0;
    enemyScore += info[step] > 0 ? 10 - step : 0;
}

getScore(score, arrow, step + 1);

내가 가진 화살의 수가 어피치의 X점에 맞힌 화살보다 많다면, 해당 점수를 어피치에게 뺏어올 수 있다. 따라서 내가 점수를 맞힌 기록인 log에 어피치보다 1발 더 많게 작성한다.
어피치가 X점에 1발 이상 맞혔던 경우, X점을 뺏어온다. 맞추지 못 했던 경우, 내 점수만 올리면 된다.
기존 점수 + X점, 화살 갯수, 재귀 횟수를 계산하고 다음 재귀함수를 실행시킨다.
재귀함수에서 벗어났을 경우, log와 enemyScore을 직전 상태로 변환.
화살을 사용하지 않고 다음 재귀함수를 호출한다.

if (step == 10) {
    log[10] = arrow;
    
    if (score - enemyScore < bestScore)
        return;
    
    if (score - enemyScore > bestScore) {
        bestScore = score - enemyScore;
        bestLog = log.clone();
        return;
    }
    
    for (int i = 10; i >= 0; i--) {
        if (log[i] == bestLog[i])
            continue;
        else if (log[i] > bestLog[i])
            bestLog = log.clone();
        return;
    }
}

재귀를 10번 다 돌았을 경우, 0점 기록에 남은 화살을 다 넣는다.
만약 내 점수 - 어피치의 점수가 bestScore를 넘기지 못 했을 경우, 그냥 반환.
bestScore를 갱신했다면 현재 화살 맞춘 log를 기록.
bestScore가 똑같다면, 문제에서 주어진 조건을 따른다.
라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.

Python

화살은 최대 10개까지 지닐 수 있고, 어피치가 한 점수에 9, 10개를 맞춘 경우는 만들어질 수 있는 경우의 수가 얼마 되지 않기 때문에 int형으로 점수를 쌓아도 문제가 없다. 그러나 처음에 주어지는 n이 상당히 많아질 경우, 해당 알고리즘은 수정이 불가피하다. 즉, 좋은 풀이는 아니다.

풀이 코드

def solution(n, info):
    score = 0
    for i in range(10):
        score += 10 - i if info[i] else 0
    
    min_log = 99999999999
    max_val = -60
    
    def shoot(arrow, apeach, ryan=0, idx=0, log=0):
        if idx == 10:
            nonlocal min_log, max_val
            
            log = log * 10 + arrow
            
            if max_val < ryan - apeach:
                max_val = ryan - apeach
                min_log = log
                
            elif max_val == ryan - apeach:
                for i in range(10):
                    A = min_log % 10 ** i
                    B = log % 10 ** i
                    
                    if A < B:
                        min_log = log
                        return
                    elif A > B:
                        return
                    
            return
        
        if arrow > info[idx] and arrow - info[idx] - 1 >= 0:
            shoot(arrow - info[idx] - 1, apeach - (10 - idx if info[idx] else 0), ryan + (10 - idx), idx + 1, log * 10 + info[idx] + 1)
        shoot(arrow, apeach, ryan, idx + 1, log * 10)
    
    shoot(n, score)
    
    if max_val <= 0:
        return [-1]
    
    min_log = list(map(int, str(min_log)))
    return [0] * (11 - len(min_log)) + min_log

해석

score = 0
for i in range(10):
    score += 10 - i if info[i] else 0

min_log = 99999999999
max_val = -60

어피치 점수 계산.

def shoot(arrow, apeach, ryan=0, idx=0, log=0):
    if idx == 10:
        nonlocal min_log, max_val
        
        log = log * 10 + arrow
        
        if max_val < ryan - apeach:
            max_val = ryan - apeach
            min_log = log
            
        elif max_val == ryan - apeach:
            for i in range(10):
                A = min_log % 10 ** i
                B = log % 10 ** i
                
                if A < B:
                    min_log = log
                    return
                elif A > B:
                    return
                
        return
    
    if arrow > info[idx] and arrow - info[idx] - 1 >= 0:
        shoot(arrow - info[idx] - 1, apeach - (10 - idx if info[idx] else 0), ryan + (10 - idx), idx + 1, log * 10 + info[idx] + 1)
    shoot(arrow, apeach, ryan, idx + 1, log * 10)

화살이 어피치의 X점 맞춘 횟수보다 많은 경우, 화살을 어피치보다 1회 더 많이 맞췄을 때와 그렇지 않을 때로 나눠 재귀를 돌린다.
재귀를 다 돌렸을 경우, log를 살펴보며 가장 낮은 점수를 더 많이 맞힌 경우를 찾는다.

shoot(n, score)

if max_val <= 0:
    return [-1]

min_log = list(map(int, str(min_log)))
return [0] * (11 - len(min_log)) + min_log

재귀함수 호출, 최고값이 0 이하일 경우 [-1] 반환, 아니라면 기록값을 숫자 하나씩 나눠 앞에 0 붙이고 반환.

여담

N = 100, info = [90, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0]이 주어질 경우, Python 풀이 같은 경우엔 [91, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]이 아닌 [9, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]이 반환된다.
비록 답은 맞지만, 그래도 어떤 풀이가 더 옳은지 생각해보자.