양궁 대회(카카오) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

어피치의 화살 정보가 먼저 주어지고 이후 쏘는 라이언의 점수를 조정해서 라이언이 어피치와의 점수를 최대로 벌려야하는 문제이다. 점수를 최대로 벌리기 위해서 라이언이 화살을 쏘는 경우를 모두 조사해서 어피치와의 점수 차이를 모두 조사하고, 그 중 최댓값을 가지는 라이언 의 화살 정보를 반환하면 되는 완전탐색 문제이다. 

 

 

재귀함수로 라이언의 화살 정보를 변경해가며 완전 탐색을 진행하며, n개의 화살을 모두 쐈다면 문제에서 제공된 점수 계산 방식을 통해 어피치와 라이언의 점수를 계산해서 두 선수의 점수 차이를 구한다. 그리고 만약 차이가 이전에 구했던 값보다 크거나 같다면 라이언의 화살 정보를 갱신해준다. 처리과정을 정리해보면 아래와 같다.

 

처리과정

1. 완전탐색을 통해서 라이언의 화살 정보를 모두 탐색한다
2. 각각의 경우에 대해 화살 n개를 모두 쐇다면, 어피치와 라이언의 점수 차이를 구한다
3. 점수 차이가 이전 값보다 크거나 같다면 라이언의 화살 정보를 갱신해준다

 

 

시간 복잡도

n개의 화살을 가지고 만들 수 있는 경우의 수는 (n+1)! 이며 n의 최댓값이 10이기 때문에 시간 내에 동작한다.

 

코드

# 라이언과 어피치의 화살 정보를 통해 점수를 구한다
def cal_score(lions, info):
    lion, apeach = 0, 0
    for i in range(11):
        if info[i] == 0 and lions[i] == 0:
            continue
        elif info[i] >= lions[i]:
            apeach += 10 - i
        else:
            lion += 10 - i

    return [lion, apeach]

# 라이언이 쏠 수 있는 모든 경우의 수를 구하고 그 중 차이가 최대인 화살 정보를 구하는 재귀함수
def dfs(lions, info, index, remain):
    global max_v, answer

    if index == 0: # 마지막 10점을 쏘는 경우, 남은 화살을 모두 쏜 후 점수를 계산한다
        lions[0]=remain
        lion, apeach = cal_score(lions, info)
        gap = lion - apeach
        if gap > 0 and gap >= max_v: # 이전 값보다 크거나 같다면 라이언의 화살을 갱신한다
            max_v = gap
            answer = lions[:]
        return

    for i in range(remain + 1): # 다음 점수에 대해 i개의 화살을 쏜다
        lions[index] = i
        dfs(lions, info, index - 1, remain - i)


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

    max_v = 0
    answer = [-1]
    lions = [0] * 11
    dfs(lions, info, 10, n)

    return answer

 

 

회고

문제를 처음 풀 때 빨리 풀려고 제한 사항 부분의 윗 부분만 읽고 로직을 작성해서 '정답이 여러개인 경우 낮은 화살을 많이 쏜 경우 출력' 과 같은 중요한 부분을 놓치고 풀었다. 기존 작성 코드에서 수정 부분을 찾으려고 했는데 오히려 시간이 더 많이 걸렸고, 너무 시간을 많이써서 다음 문제로 넘겼다. 다음에 풀게 되면 아래 사항에 좀 더 집중에서 문제를 풀자.

1. 제한 사항, 입출력 예시까지 분석하고 설계에 들어간다
2. 만약 설계에서 잘못되었다면, 이전 코드를 수정하기 보다는 다시 작성하는 것이 효율적이다(개인적으로)