2022 KAKAO BLIND RECRUITMENT 양궁대회 Lv. 2

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

파이썬 소스: https://bit.ly/3w8cfDR

 

 이런 문제를 어떤 방식으로 풀어야 하는지, 접근하는 방법을 알아보겠습니다.

- 어피치는 이미 모든 화살을 과녁판에 쏘았습니다.

- 원에 맞출 때 마다, 점수가 올라가는게 아닙니다.

- 어피치 보다 1발 더 쏘아야, 해당 원의 점수를 라이언이 얻을 수 있습니다.

 

여기까지 정리해보면, infor[x]의 값을 보고 라이언이 할 수 있는 행동은 2가지입니다.

1. x번 (즉, 10 - x 점)에 info[x] + 1발의 화살을 쏩니다. 10-x 점을 라이언이 얻습니다.

2. x번에 아무 화살도 쏘지 않고, 화살을 아껴 둡니다.

여기서, 앞의 1번에서 왜 라이언이 ‘info[x] +1 발’을 쏴야 하나? ‘info[x] +2 발’을 쏘면 안되는 건가?

이런 궁금증이 생길 수 있습니다. 아래 2가지 이유 때문에 +1입니다.

a. +1을 쏘든, +2를 쏘든 라이언이 얻는 점수는 같습니다.

b. 문제에서 ‘가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.’ 라고 기술하고 있습니다.

따라서 화살을 최대한 아끼면서, 라이언이 가장 큰 점수 차로 이기도록 하려면, 어피치 보다 딱 한발만 더 쏴서, 해당 점수를 라이언이 얻어야 합니다. 아낀 화살은 모두 0점에 모두 쏘아야 합니다. 0점이 가장 낮은 점수이기 때문입니다. 같은 이유로, 해당 점수를 얻지 않겠다면, 해당 점수의 원에 화살을 쏘지 않습니다.

 

10점부터 0점까지를 일종의 단계가 한 단계씩 있다고 본다면, 이 문제에서는 총 11단계가 있다고 할 수 있습니다.

각 단계 마다, 라이언은 어피치 보다 1발 더 쏠지, 아니면 쏘지 않고 다음단계로 갈지 2가지로 분기합니다. 하지만, 분기하기 전에, 다음단계로 진행하다가 중간에 멈추어야 하는 조건이 있습니다. 화살을 모두 쏘았을 때입니다.

이렇게 매 단계 마다 2가지 분기와, 화살을 모두 쏜 경우를 고려하여, 재귀함수를 작성하여 이 문제를 풀 수 있습니다.

매 단계 마다 최대 2가지로 분기할 수 있고, 마지막 단계에 도착하거나, 중간에 모든 화살을 쏘게 되면, 어피치가 쏜 화살과 비교해서, 라이언의 점수를 구할 수 있습니다. 경우에 따라서는, 같은 점수를 얻지만, 화살을 서로 다른 점수에 쏜 경우도 있을 수 있습니다. 이 경우에는 앞에서 알아본 b 번의 규칙에 따라서, 2가지 분기중 어느 값을 선택할지 판단할 수 있습니다.

 

위의 b번 규칙에 따라서, 비교하는 함수부터 코딩해보겠습니다.

def my_cmp(ans1, ans2):     shot1, shot2 = ans1[1], ans2[1]     for idx in range(10, -1, -1):         v1 = shot1[idx]         v2 = shot2[idx]         if v1 > v2:             return ans1         elif v1 < v2:             return ans2     return ans2

ans1, ans2둘은 리스트로, 0번째에는 라이언점수 – 어피치점수가 저장되어 있고, 1번째에는 매 단계별로 쏜 화살의 개수가 저장되어 있습니다. 점수가 납은 원을 쏜 화살이 많은 쪽이 선택되어야 함으로, 인덱스 10부터 1씩 감소하면서, 화살의 개수를 비교하여, 개수가 큰 쪽을 리턴합니다.

함수 my_cmp()는 라이언점수 – 어피치점수가 같은 경우에만 호출됩니다.

이번에는 점수를 계산하는 함수를 코딩해보겠습니다.

def jumsu(shot_by_apeach, shot_by_ryan):     score_apeach, score_ryan = 0, 0     for idx in range(len(shot_by_apeach)):         if shot_by_ryan[idx] > shot_by_apeach[idx]:             score_ryan += (10 - idx)         elif shot_by_apeach[idx] > 0:             score_apeach += (10 - idx)     return score_ryan - score_apeach

함수 인자로는 어피치가 매 단계바다 쏜 화살, solution()함수의 info 인자입니다. 라이언이 쏜 화살은 shot_by_ryan 리스트 인자로 주어집니다. 두 리스트의 길이는 11로 0부터 10인덱스까지 있습니다. 매 단계 마다, 라이언이 쏜 화살이 많으면, 해당원의 점수(10 – idx)를 라이언이 얻게되고,, 그렇지 않고 어피치가 쏜 화살의 개수가 1이상이거나, 어피치가 쏜 화살의 개수가 많다면, 해당원의 점수(10 – idx)를 어피치가 얻게 됩니다.

라이언과 어피치의 점수 차이가 가장 큰 것을 찾아야 하기에, 라이언의 점수에서 어피치의 점수를 뺀 값을 리턴합니다.

 

solution()함수는 아래와 같이 rec()함수를 호출합니다.

def solution(n: int, info: List[int]):     answer = rec(0, n, info, [])     if answer[0] <= 0:         return [-1]     return answer[1]

함수 rec의 각 인자는 4개로 각각 아래의 값을 가집니다.

depth: int: : 각 단계를 뜻하고, 10 – depth가 해당 원의 점수 입니다.

remained_arrow: int : 라이언에게 남은 화실 수

info: List[int] : 어피치가 각 단계 마다 쏜 화살 수를 가지고 있는 리스트 입니다.

shot_by_ryan: List[int] : 라이언이 각 단계 마다 쏘는 화살 수를 가지고 있는 리스트 입니다.

함수 rec()의 리턴값은 리스트로 0번째에는 라이언점수 – 어피치점수 값이 들어 있구요, 1번째에는 라이언이 각 단계 마다 쏜 화살 수를 리스트로 가지고 있습니다.

answer[0]이 0보다 작으면, 어피치의 점수가 더 크다는 의미입니다. [-1]을 리턴합니다.

answer[0]이 0과 같아도, 어피치의 승리이기 때문에, [-1]을 리턴합니다.

앞의 2가지 경우 이외에는 라이언의 점수가 큰 경우로, 라이언이 쏜 화살을 리턴합니다.

 

매 단계 마다 재귀호출을 할 rec()함수를 코딩해 보겠습니다.

def rec(depth: int, remained_arrow: int, info: List[int], shot_by_ryan: List[int]):     if depth == len(info) or remained_arrow == 0:         shot_by_ryan += [0] * (len(info) - len(shot_by_ryan))         shot_by_ryan[10] += remained_arrow         return [jumsu(info, shot_by_ryan), shot_by_ryan]

변수 depth는 인덱스 값이므로 0 부터 최대 10까지 가능합니다. 11이 되었다는건 모든 단계를 거처 왔다는 의미임으로 점수를 계산해서 리턴해야 합니다.

라이언에게 남은 화살이 없을 때도, 다음 단계로 진행하지 못하기 때문에, 라이언의 점수를 계산해서 리턴해야 합니다.

라이언이 쏜 화살을 저장하는 리스트의 길이가 11보다 작다면, 길이를 11로 맞춰주기 위해서, [0]을 더해 줍니다.

남은 화살이 있다면, 마지막 0점(shot_by_ryan[10])에 모두 더해 줍니다.

점수 계산을 하고, 점수와 라이언이 쏜 화살 리스트를 리턴합니다.

 

ans1 = [-1, [0] * 11] if remained_arrow - (info[depth] + 1) >= 0:     ans1 = rec(depth + 1, remained_arrow - (info[depth] + 1), info, shot_by_ryan + [(info[depth] + 1)]) ans2 = rec(depth + 1, remained_arrow, info, shot_by_ryan + [0]) if ans1[0] > ans2[0]:     return ans1 elif ans1[0] < ans2[0]:     return ans2 return my_cmp(ans1, ans2)

리스트 ans1을 -1 과 [0]을 11개 가진 리스트로 초기화 합니다. 현재 단계에서 남은 화살을 모두 쏘아도, 어피치가 쏘아놓은 화살의 개수가 더 많다면, 화살을 쏠 필요가 없습니다. 따라서, rec()가 호출되지 않을 경우도 있기 때문에, ans1을 미리 초기화 해두는 것입니다.

 화살을 쏘는 경우는 다음 단계를 표시하기 위해서 depth +1을 하구요, 남은 화살에서 어피치가 쏜 화살 수 +1 을 빼줍니다. Info는 그대로 전달하구요, 라이언이 쏜 화살 수를 shot_by_ryan에 추가해 줍니다.

리스트 ans2는 이번 단계에서 화살을 쏘지 않고, 다음 단계로 넘어가는 것입니다. depth에 +1을 하고, 라이언이 쏜 화살이 0개 임으로, shot_by_ryan에 + [0]을 해줍니다.

ans1 과 ans2의 점수 차이를 비교해서, 점수가 큰 것을 리턴합니다. 점수가 같다면, 앞에서 만들어둔 my_cmp()를 통해서 낮은 점수에 쏜 화살이 많은 경우를 리턴하게 됩니다.

위와 같이 힘수 rec()를 재귀 호출해서, 모든 경우의 수를 방문해 보면, 이 문제를 풀 수 있습니다.

 

궁금한 문제, 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래에 있습니다.

from typing import List def solution(n: int, info: List[int]):     answer = rec(0, n, info, [])     if answer[0] <= 0:         return [-1]     return answer[1] def rec(depth: int, remained_arrow: int, info: List[int], shot_by_ryan: List[int]):     if depth == len(info) or remained_arrow == 0:         shot_by_ryan += [0] * (len(info) - len(shot_by_ryan))         shot_by_ryan[10] += remained_arrow         return [jumsu(info, shot_by_ryan), shot_by_ryan]     ans1 = [-1, [0] * 11]     if remained_arrow - (info[depth] + 1) >= 0:         ans1 = rec(depth + 1, remained_arrow - (info[depth] + 1), info, shot_by_ryan + [(info[depth] + 1)])     ans2 = rec(depth + 1, remained_arrow, info, shot_by_ryan + [0])     if ans1[0] > ans2[0]:         return ans1     elif ans1[0] < ans2[0]:         return ans2     return my_cmp(ans1, ans2) def jumsu(shot_by_apeach, shot_by_ryan):     score_apeach, score_ryan = 0, 0     for idx in range(len(shot_by_apeach)):         if shot_by_ryan[idx] > shot_by_apeach[idx]:             score_ryan += (10 - idx)         elif shot_by_apeach[idx] > 0:             score_apeach += (10 - idx)     return score_ryan - score_apeach def my_cmp(ans1, ans2):     shot1, shot2 = ans1[1], ans2[1]     for idx in range(10, -1, -1):         v1 = shot1[idx]         v2 = shot2[idx]         if v1 > v2:             return ans1         elif v1 < v2:             return ans2     return ans2