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

문제 요약

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

라이언과 어피치가 양궁대회를 한다.
어피치가 쏜 n발의 화살에 대한 정보가 info에 담겨 주어진다.
이때 라이언이 가장 큰 점수차로 이기는 화살 조합을 반환하고 이길 수 없다면 [-1]을 반환한다.
라이언이 이기는 경우는 특정 과녁 점수에 맞힌 화살의 개수가 무조건 어피치보다 큰 경우이다.
같거나 작다면 어피치가 이기게 된다.
이기는 경우가 여러 개일 때는 가장 낮은 점수를 더 많이 맞춘 조합을 반환해야한다.

접근

처음봤을 때 백트랙킹을 이용해 모든 경우를 일일이 다 훑어봐야겠다고 생각했다.
라이언이 가장 효율적으로 어피치를 이기려면 어피치보다 특정 과녁 점수에 맞친 화살의 개수가 1만큼만 크면 된다.
따라서 info 배열에서 각 원소값에 1을 더한 값을 ryan 배열에 넣어주었다.
백트랙킹을 통해 ryan배열에 있는 값들을 하나씩 더해가며 총 n개의 화살이 되었을 때 어피치와의 승부를 따져주었다.

라이언과 어피치의 승부를 표시하기 위해 diff 배열을 사용했다.

diff값이 1이면 라이언이 이겼을 때이고, diff값이 0이면 어피치가 이겼을 때이다. -1이면 아무도 맞히지 못한 과녁이다.

가장 큰 점수 차를 가진다면 score 변수에 저장해주었다.

그리고 가장 큰 점수 차를 가지는 경우의 수가 여러개일 때 화살 조합을 따져줘야하기 때문에 화살 조합을 result에 저장해주었다.

모든 코드를 작성하고 나서 알게된 사실.

처음부터 로직이 잘못되었다.

dfs에 조건을 적절히 걸어줘야한다.

한번 들어갔다가 arrow == n가 처음으로 성립하면 다른 경우는 따져주지 않는다.....

다시 도전

코드

import copy


def solution(n, info):
    def get_dif(check, max_score):
        nonlocal result
        # 승부에 따른 점수의 차 구하기
        score = 0
        for i in range(11):
            if info[i] < check[i]:
                score += 10 - i
            elif info[i] >= check[i] and info[i] != 0:
                score -= 10 - i

        # 최대 점수 차, 라이언의 화살 조합 저장
        if score > max_score:
            max_score = score
            # 화살 조합 저장
            result = copy.deepcopy(check)

        elif score == max_score:
            # 이전에 구한 화살 조합과 비교
            for i in range(10, -1, -1):
                if result[i] > check[i]:
                    result = copy.deepcopy(check)
                    return max_score

        return max_score

    def dfs(idx):
        nonlocal arrow
        nonlocal max_score

        if idx > 10 or arrow > n:
            return

        # (10-idx)점짜리 과녁에 화살 ryan[idx]번 쏜 경우 추가
        arrow += ryan[idx]
        check[idx] = ryan[idx]

        if arrow == n:  # n개의 화살수를 다 채웠다면 최대 점수차 구하기
            max_score = get_dif(check, max_score)

            # 해제
            arrow -= ryan[idx]
            check[idx] = 0

            dfs(idx + 1)

        dfs(idx + 1)

    arrow = 0
    max_score = 0
    ryan = [i + 1 for i in info]
    check = [0] * 11
    result = [0] * 11
    dfs(0)

    return result

 

참고 코드

def solution(n, info):
    global max_gap, answer

    answer = [-1]
    score = [0] * 11
    max_gap = 0

    def is_winner_with_gap(score):
        a = 0  # 어피치 점수
        b = 0  # 라이언 점수

        for i in range(len(info)):
            if info[i] > 0 or score[i] > 0:
                if info[i] >= score[i]:
                    a += 10 - i
                else:
                    b += 10 - i
        return (b > a, abs(a - b))

    def dfs(L, cnt):
        global max_gap, answer
        if L == 11 or cnt == 0:
            is_winner, gap = is_winner_with_gap(score)
            if is_winner:
                if cnt >= 0:  # 화살이 남은 경우
                    score[10] = cnt  # 0점에 쏴도 이김

                if gap > max_gap:  # 갭이 더 큰 경우로 업데이트
                    max_gap = gap
                    answer = score.copy()

                elif gap == max_gap:  # 가장 낮은 점수를 많이 맞힌 경우로 업데이트
                    for i in range(len(score)):
                        if answer[i] > 0:
                            max_i_1 = i
                        if score[i] > 0:
                            max_i_2 = i
                    if max_i_2 > max_i_1:
                        answer = score.copy()

            return

        # k점을 어피치보다 많이 맞추거나 아예 안맞추거나
        if cnt > info[L]:  # 어피치가 L 과녁에 쏜 화살보다 남은 화살의 개수가 크면
            score[L] = info[L] + 1
            dfs(L + 1, cnt - (info[L] + 1))
            score[L] = 0

        # L 과녁에 어피치보다 더 많이 쏠 수 없다면 패스
        dfs(L + 1, cnt)

    dfs(0, n)

    return answer

 

출처 https://velog.io/@syong_e/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%96%91%EA%B6%81%EB%8C%80%ED%9A%8CDFS-%ED%8C%8C%EC%9D%B4%EC%8D%AC