코딩테스트 스터디 - 프로그래머스 양궁대회 (python)

문제

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

프로그래머스

 

요약

어피치와 라이언(나)이 양궁게임을 한다.

이 양궁게임에는 과녁이 0~10점까지 있으며, 각 점수에 더 많이 쏜 사람이 해당 점수를 가져간다.

같은 수 만큼 쏘면 어피치가 점수를 가져가며, 둘 다 0개를 쏜 경우 아무도 점수를 얻지 않는다.

이렇게 점수 합산을 해 내가 최대 점수 차이로 이길 수 있는 방법을 반환해야한다.

같은 점수차이가 있다면 가장 낮은 점수 화살이 많은 쪽을 반환한다.

의식의 흐름

이 양궁게임은 특정 점수를 먹냐 안먹냐를 결정해야한다.

예를들어 어떤 점수를 어피치가 4개 쐈으면, 그 점수를 먹으려면 5(4+1)개를 쏴야하고, 안먹을거면 0개를 쏴야한다.

여기서 어려운 점은 내 결과에 따라 어피치의 점수도 바뀐다는 것인데,

이를 없애기 위해 어피치가 쏜 점수는 점수 획득량을 2배로 하면 된다.

그러면 어피치의 점수를 고정하고 내 점수가 어피치의 점수보다 높은지만 확인하면 된다.

 

모든 경우를 탐색해도 2^10 가지만 탐색해도 되고,

최소 화살 수는 언제든 나올 수 있기 때문에 모든 경우를 탐색하는 DFS 기반 BackTracking 방식을 사용하기로 했다.

Best First Search도 생각해봤으나, Huristic 부분을 어떻게 정해야할지 감이 안잡혀서 모든 경우를 탐색하기로 했다.

BFS를 안쓴 이유는 그냥 개인적으로 DFS 연습을 하고싶어서다.

구현

자료구조

계산을 쉽게하기 위해 두 리스트를 만들었다.

stake : 각 과녁별 얻는 점수 (어피치가 쏜 쪽 과녁은 2배로 보정했다.)

limit : 각 과녁별로 득점을 위해 필요한 화살 수 (어피치가 과녁에 쏜 화살 수 + 1)

 

DFS를 위해 별도의 stack 없이 재귀함수를 이용했다.

result 리스트에 라이언이 과녁별로 쏜 화살 수를 기록해 관리한다.

재귀함수를 이용해 result를 stack에 넣을 때마다 복제할 필요가 없다.

함수의 인자로 전달되는 State 는

State = 현재 탐색 index, 상대점수 (내점수 - 어피치점수), 남은 화살 수

알고리즘

문제 풀이의 핵심은 DFS를 담당하는 solve함수다.

탐색은 10점~1점 순으로 탐색하며

solve(state)함수는 아래와 같이 작동한다.

 

if 상대점수 > 0:

    현재 정답과 비교해 점수차이가 더 크거나 낮은 점수 화살이 많으면 정답 overwrite

if (탐색 index == 10) or (남은 화살 수 == 0):

     return

이번 index 점수를 먹을 때의 solve 실행 (화살 수가 남아 있을 때만)

이번 index 점수를 안 먹을 때의 solve 실행

 

마지막까지 탐색이 끝나면 정답을 반환한다.

코드

limit, stake 변수 등을 만들기 잘 한 것 같다.

복잡해보이는 문제를 단순화 하는게 이번 문제의 포인트 같다.

재귀함수 기반 DFS를 쓸 때는 변수 값을 전달하고 저장하는게 복잡해져서 왠만해선 안하고 싶다.

하지만 result 같은 state변수를 복사하지 않아도 되는 건 좋은 것 같다.

접근은 잘 했는데 DFS 구현하는 부분에서 python 문법을 까먹어서 시간이 오래걸렸다. 

python에서 전역변수를 사용하기 전에 global 선언을 꼭 해주는 것을 잊지말자 !

 

'''
    문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/92342
'''

answer = [-1, [-1]]
def solve(x, score, arrow, stake, limit, result):
    global answer
    if score > 0:
        result[10 ] = arrow
        if comp(answer, (score, list(result))) < 0:
            answer = (score, list(result))
    if x == 10 or arrow == 0: 
        return
    #점수먹기
    if arrow >= limit[x]:
        result[x] = limit[x]
        solve(x+1, score + stake[x], arrow - limit[x], stake, limit, result)
    #안먹기
    result[x] = 0
    solve(x+1, score, arrow, stake, limit, result)
    
def comp(a,b):
    if a[0] == b[0]:
        for i in range(10, -1, -1):
            if a[1][i] == b[1][i]:
                continue
            return a[1][i] - b[1][i]
        return 0
    else:
        return a[0] - b[0]
    
def solution(n, info):
    
    #state = x점을 먹고/안먹고 결정 한 후 내점수, x+1, 리스트
    stake = [(10-i)*2 if info[i] > 0 else 10-i for i in range(len(info))] #과녁 점수 별 얻는 점수 (2배보정)
    limit = [x + 1 for x in info] #과녁 점수 별 득점을 위해 필요한 화살 수 (1 or 어피치+1)
    score = -sum([(10-i) if info[i] > 0 else 0 for i in range(len(info))]) #어피치와의 상대점수
    
    arrow = n
    result = [0 for i in range(11)]
    x = 0 #현재 확인할 index
    solve(x, score, arrow, stake, limit, result)
    
    return answer[1]