[2022 KAKAO BLIND RECRUITMENT] 양궁대회

문제 설명

프로그래머스

---

풀이 방법

• 접근 방식

    ◦  라이언이 어피치를 가장 큰 점수로 차이로 어피치를 이길 수 있는 경우를 구해야 하는 문제이다.

          -  점수차이가 나는데 특별한 수학적 규칙이 없고, 라이언이 화살을 어떻게 쏘는가 그 결과에 달려있다.

          -  화살을 쏠 수 있는 모든 경우의 수를 구하고, 그 결과를 비교해 점수차의 최댓값을 구하는 문제이다.

    ◦  보통 여러가지 경우의 수에 대한 결과를 비교할 땐 BFS를 사용하는게 편하다. 이 문제도 마찬가지!

 

• 핵심 아이디어

    ◦  10점 ~ 0점 과녁을 순회하면서, 각 점수 과녁에서 라이언이 할 수 있는 선택은 2가지이다.

          -  화살을 쏘지 않고 아껴둔다. (사용한 화살 : 0개)

          -  어피치가 쏜 화살보다 1개 더 쏜다. (사용한 화살 : 어피치가 쏜 화살 +1개)

    ◦  과녁은 10점 ~ 0점 총 11개 이고, 선택은 2가지 이니까 총 2의 11제곱에 대한 경우의 수를 자식 노드가 2개인 이진트리로 집계한 후
         결과를 비교하면 된다.

 

• 알고리즘

    ◦  이진트리 BFS

          -  각 점수 과녁을 순회하면서 화살을 쏘거나, 쏘지 않거나로 자식 노드를 확장해 나간다.

          -  노드 확장 종료 조건 = 화살을 다 쐈음 or (10점~0점 과녁 순으로 순회할 때)현재 과녁이 마지막 과녁임

              -  현재 과녁이 마지막 과녁인 경우, 남은 화살을 전부 쏜다.

              -  또한 어피치보다 무조건 1개 더 쏘는 상황이 반복되다보면 라이언이 쏠 수 있는 화살 개수보다 더 쏘게되는 상황이
                  발생할 수 있다. 이는 경기상에서 고려하지 않는 상황이므로, 이 케이스는 무시하는 로직을 추가해 줘야 한다.

          -  노드 확장이 종료되면 그 케이스의 라이언과 어피치의 점수 차이를 구한다.

          -  모든 경우의 수를 돌면서, 점수 차이가 최대가 되는 값을 계속 업데이트한다.

---

파이썬 코드

def solution(n, info):
    # set variables
    bfs = [(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])]
    maxScore = 0
    answer = []
    
    while(bfs):
        # 현재 쏘려는 점수, 과녁 현황
        idx, arrowList = bfs.pop(0)
        
        # 종료 조건1 : 화살을 모두 쏜 경우
        if(sum(arrowList) == n):
            apeach, lion = 0, 0
            # 점수 차이 집계
            for i in range(11):
                if(arrowList[i]+info[i] == 0):
                    continue
                if(arrowList[i] <= info[i]):
                    apeach += 10 - i
                else:
                    lion += 10 - i
            # 라이언이 이긴 경우 : 점수 차이 최댓값 업데이트
            if apeach < lion:
                if maxScore > (lion - apeach):
                    continue
                if maxScore <= (lion - apeach):
                    maxScore = lion - apeach
                    answer = arrowList.copy()
            
        # 종료 조건2 : 화살을 오버해서 쏜 경우 (무시)
        elif(sum(arrowList) > n):
            continue
        
        # 종료 조건3 :  마지막 과녁인데 화살이 남은 경우 (남은 화살을 다 쏜다)
        elif(idx == 10):
            arrowList[10] = n - sum(arrowList)
            bfs.append((-1,arrowList))
        
        # 경기 진행중
        else:
            # 어피치보다 1발 더 쏘기
            temp = arrowList.copy()
            temp[idx] = info[idx]+1 
            bfs.append((idx+1, temp))
            
            # 쏘지 않기
            temp = arrowList.copy()
            temp[idx] = 0 
            bfs.append((idx+1, temp))
    
    # return answer
    if(not answer):
        return [-1]
    return answer