[프로그래머스] 양궁대회(파이썬)-카카오 인턴쉽 기출

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

프로그래머스

문제풀이 방법이 다양한데

저는 백트레킹 기법을 썼습니다.

완전탐색하듯이

모든 케이스를 다 구하는 경우를 가정했습니다.

from copy import deepcopy


def dfs(depth, max_depth, shoot, max_shoot, lion, appach):
    global answer
    global max_cha

    if shoot > max_shoot:
        return

    if depth == max_depth or shoot == max_shoot:

        tmp = lion[-1]

        # 화살이 남았으면 0에 다 쏜다
        lion[-1] += max_shoot - shoot
        num_l = 0
        num_a = 0
        for i in range(10):
            if lion[i] == 0 and appach[i] == 0:
                continue
            if lion[i] >= appach[i]:
                num_l += 10 - i
            else:
                num_a += 10 - i
        cha = abs(num_l - num_a)

        if num_l > num_a and cha > max_cha:

            answer = deepcopy(lion)
            max_cha = cha

        # 만약 차가 같다면, 낮은거 더 많은 쪽을 받아준다            
        elif num_l > num_a and cha == max_cha:

            for k in range(10, -1, -1):
                if answer[k] > lion[k]:
                    break
                elif answer[k] < lion[k]:
                    answer = deepcopy(lion)
                    break

        lion[-1] = tmp

        return

    now = appach[depth]
    if shoot + now <= max_shoot:
        lion[depth] += now + 1
        dfs(depth + 1, max_depth, shoot + now + 1, max_shoot, lion, appach)
        lion[depth] -= now + 1

    dfs(depth + 1, max_depth, shoot, max_shoot, lion, appach)


answer = []
max_cha = 0


def solution(n, info):
    global answer
    tmp = [0] * 11
    dfs(0, 11, 0, n, tmp, info)
    print(answer)
    if answer == []:
        ans = [-1]

    else:

        ans = answer
    return ans

 

https://osnim.tistory.com/entry/%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%8C-%ED%8C%8C%EC%9D%B4%EC%8D%AC

프로그래머스 양궁대회 (파이썬)

https://velog.io/@mrbartrns/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%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%8C-python

[알고리즘] 프로그래머스 - 양궁대회 (python)

문제를 풀긴 풀었는데...

다른 사람들 풀이를 보고 놀랐습니다.

비트마스킹이라니...

아...벌써 머리가 아픕니다.

고노 와타시한테 이런 고난을 주시나요.

하...비트마스킹도 공부해놔야하네요...

(고달프다 ㅠㅠ)