프로그래머스 Lv2 양궁대회 Python

1. 2022 KAKAO BLIND RECRUITMENT

코딩테스트 연습 | 프로그래머스 스쿨

정답 코드

win = [1 for _ in range(11)]
app = []
maxScore = 0
maxV = [0 for _ in range(11)]
def comparison(V, tmp):
    r = 0
    a = 0
    for i in range(11):
        if app[i] < tmp[i]:
            r += 10 - i
        elif app[i] != 0:
            a += 10 - i
    return r - a

def dfs(S, cnt, V, n):
    if cnt > n:
        return
    if S == 11:
        if cnt <= n:
            global maxScore, maxV, app
            nowCnt = 0
            tmp = [0 for _ in range(11)]
            for idx, cnt in V:
                tmp[idx] += cnt
                nowCnt += cnt
            if nowCnt != n:
                tmp[10] += n - nowCnt
            score = comparison(V, tmp)
            if maxScore < score:
                maxScore = score
                maxV = tmp[:]
            elif score > 0 and maxScore == score:
                for i in range(10, -1, -1):
                    if maxV[i] < tmp[i]:
                        maxV = tmp[:]
                        break
                    elif maxV[i] > tmp[i]:
                        break
        return
    dfs(S+1, cnt+win[S], V+[(S, win[S])], n)
    dfs(S+1, cnt, V, n)
    return

def solution(n, info):
    global app
    for i in range(11):
        win[i] += info[i]
    app = info
    dfs(0, 0, [], n)
    result = maxV
    if sum(result):
        return result
    else:
        return [-1]

풀이 방식

- 어피치보다 한 발 더 쏘면 이기는 거니까 1씩 더한 값을 배열로 만들었다.

- 만든 배열을 바탕으로 전체 쏜 화살을 계산해서 비교해준다.

- 현재 배열과 아피치가 쏜 화살리스트를 비교했을 때 높으면 값을 저장하고 배열도 저장한다.

- 하지만 여기서 중요한 점

    - 내가 만든 낮은 점수를 많이 쐈는지 비교하는 코드가 틀려서 오래 걸렸다.

    - 반복문을 종료할 때 클 때만 종료하는 것이 아니라 작을 때도 비교할 필요가 없으므로 종료시켜야 했다.
- 시간초과에 제약이 있었는지는 모르지만 가지치기를 했기 때문에 백트래킹 알고리즘을 적용했다고 본다.

느낀점

- 다 풀었어도 내가 맞다고 생각해도 통과되지 않으면 처음부터 다시 보는 습관을 들이자.