LV2 [KAKAO] 양궁대회

---

문제

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

프로그래머스

 

풀이

 

완전탐색으로 풀었다. 

 

문제 풀 때 주의해야하는거는 

 

1. 라이언이 어피치를 이겨야 한다.

2. 이길 때, 가장 큰 점수차로 이겨야한다.

3. 가능하면 작은 점수의 화살을 많이 맞춰 이겨야한다.

 

이 세가지 요소이다.

 

따라서 나는 가장 작은 점수부터 맞추는 방식으로 접근했다.

0점부터 -> 10점까지 접근하면서 모든 경우의 수를 체크해본다. (해당 인덱스의 점수를 얻거나, 포기하거나)

이 때 점수를 얻기위해서는 최소한의 화살을 사용하는 것이 좋으므로, 어피치의 화살 개수 +1 개로 설정해준다.

 

그렇게 화살을 다 썼다면 점수차이를 비교해본다.

만약 기존의 점수차보다 크다면, 정답배열을 갱신해준다.

 

화살을 다 쓴게 아니라, 인덱스를 벗어났을 경우에는 남는 화살을 처리해줘야 한다.

우리가 이기는 경우는 다 처리해주고 왔기에, 최대한 작은 점수에 많은 화살을 사용해주어야 한다.

그래서 작은 점수부터 순회하면서 남은 화살을 다 사용해준다.

 

추가적으로 이런식으로도 화살을 다 쓰지 못했다면 이기는 점수에 카운터해주는 로직도 만들었는데,

빼고 해봐도 정답으로 인정받았다. 그런 케이스는 없는거 같다.

 

 

코드

import copy

final_ans = []
sub = -1
def getanswer(info, arrow, answer):
    global final_ans, sub

    # 화살이 남아있다면 버림용도로 사용한다. (어피치가 이기는데에 사용)
    if arrow>0:
        # 뒤에서부터 (가장 낮은 점수부터) 남은 화살을 배정해준다.
        for i in range(10, -1, -1):
            # 화살 다쓰면 끝!
            if arrow == 0 :
                break

            # 라이언에 점수가 배정되어 있지 않고, 어피치도 0이 아니라면
            if answer[i] == 0 and info[i] != 0:
            # 화살이 해당 인덱스보다 적거나 같을때 -> 그냥 다 박아준다. (같으면 어피치가 이김)
                if arrow <= info[i]:
                    answer[i] = arrow
                    arrow = 0
                else:
                    # 아니라면 같은 개수 박아주고, 화살을 차감해준다.
                    answer[i] = info[i]
                    arrow -= info[i]

    # 위의 경우에도 화살을 다 못쓸 수 있음
    # 그러면 낮은 점수중 라이온이 이기는 카운터에 남은화살을 다 넣어준다.
    if arrow>0:
        for i in range(10, -1, -1):
            if answer[i] > info[i]:
                answer[i] += arrow
                break

    a = 0
    l = 0

    for i in range(11):
        # 라이언이 크다면, 라이언이 점수를 먹는다.
        if answer[i] > info[i]:
            l += (10-i)
        # 그 외에는 어피치가 먹는다.
        if answer[i] <= info[i] != 0:
            a += (10-i)

    # 라이언이 이겼을 경우에
    if l > a:
        # 기존 차 보다 같거나 크다면
        if sub < l-a:
            sub = (l-a)
            final_ans = copy.deepcopy(answer)

def recursive(idx, arrow, info, answer):
    # 점수지를 다 돌았으면 정답 로직 수행
    if idx <0:
        getanswer(info, arrow, answer)
        return

    # 화살이 더 없으면 정답로직 수행
    if arrow == 0:
        getanswer(info, arrow, answer)
        return

    # 현재 화살이 어피치보다 많을때, 점수를 먹어준다. +1개로 제한
    if info[idx] < arrow:
        temp_answer = copy.deepcopy(answer)
        temp_answer[idx] = info[idx]+1
        recursive(idx-1, arrow - (info[idx]+1), info, temp_answer)
    recursive(idx-1, arrow, info, answer)

def solution(n, info):
    answer = [0] * 11
    recursive(10, n, info, answer)

    # 만약 이길 수 없다면
    if sub == -1:
        return [-1]
    return final_ans

 

후기

 

문제 접근은 수월하게 한것에 비해 자잘한 오류를 잡는데에 시간이 오래걸렸다.

같은 화살 개수면 어피치가 먹는것도 간과하고 부등호를 잘못 설정했고, 점수는 10-i 로 해야하는데 인덱스가 11인거에 꽂혀 11-i 로 점수를 계산하기도 했다. 구현부분에 있어서 이런 디테일함을 잘 챙기는것이 시간 단축의 지름길인 거 같다.