문제 설명
카카오배 양궁대회가 열렸습니다.
라이언
은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치
입니다.
카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다.
- 어피치가 화살
n
발을 다 쏜 후에 라이언이 화살n
발을 쏩니다. - 점수를 계산합니다.
- 과녁판은 아래 사진처럼 생겼으며 가장 작은 원의 과녁 점수는 10점이고 가장 큰 원의 바깥쪽은 과녁 점수가 0점입니다.
- 만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 단, a = b일 경우는 어피치가 k점을 가져갑니다. k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져가는 것을 유의하세요. 또한 a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.
- 예를 들어, 어피치가 10점을 2발 맞혔고 라이언도 10점을 2발 맞혔을 경우 어피치가 10점을 가져갑니다.
- 다른 예로, 어피치가 10점을 0발 맞혔고 라이언이 10점을 2발 맞혔을 경우 라이언이 10점을 가져갑니다.
- 모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산합니다.
- 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.
현재 상황은 어피치가 화살 n
발을 다 쏜 후이고 라이언이 화살을 쏠 차례입니다.
라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 n
발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구하려고 합니다.
화살의 개수를 담은 자연수 n
, 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info
가 매개변수로 주어집니다. 이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 n
발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]
을 return 해주세요.
제한사항
- 1 ≤
n
≤ 10 info
의 길이 = 11- 0 ≤
info
의 원소 ≤n
info
의 원소 총합 =n
info
의 i번째 원소는 과녁의10 - i
점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.)
- 0 ≤
- 라이언이 우승할 방법이 있는 경우, return 할 정수 배열의 길이는 11입니다.
- 0 ≤ return할 정수 배열의 원소 ≤
n
- return할 정수 배열의 원소 총합 =
n
(꼭 n발을 다 쏴야 합니다.) - return할 정수 배열의 i번째 원소는 과녁의
10 - i
점을 맞힌 화살 개수입니다. ( i는 0~10 사이의 정수입니다.) - 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
- 가장 낮은 점수를 맞힌 개수가 같을 경우 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
- 예를 들어,
[2,3,1,0,0,0,0,1,3,0,0]
과[2,1,0,2,0,0,0,2,3,0,0]
를 비교하면[2,1,0,2,0,0,0,2,3,0,0]
를 return 해야 합니다. - 다른 예로,
[0,0,2,3,4,1,0,0,0,0,0]
과[9,0,0,0,0,0,0,0,1,0,0]
를 비교하면[9,0,0,0,0,0,0,0,1,0,0]
를 return 해야 합니다.
- 0 ≤ return할 정수 배열의 원소 ≤
- 라이언이 우승할 방법이 없는 경우, return 할 정수 배열의 길이는 1입니다.
- 라이언이 어떻게 화살을 쏘든 라이언의 점수가 어피치의 점수보다 낮거나 같으면
[-1]
을 return 해야 합니다.
- 라이언이 어떻게 화살을 쏘든 라이언의 점수가 어피치의 점수보다 낮거나 같으면
풀이
본 문제가 아마 실제 2022 카카오 블라인드 1차 코딩테스트
에서 불합 여부를 가르는 문제였을 것이다. 본 문제까지 모든 문제에 대하여 완벽하게 풀어냈다면 1차 합격을 했을 것이다. 문제 유형은 빠지지 않고 한 문제씩 중간 번호즈음에서 출제되고 있는 완전탐색
문제이다.
우선 이 문제는 완전탐색
을 떠올리는 것 자체가 가장 핵심적인 단계이다. 최대 10
개의 화살이 있고 맞출 수 있는 과녁의 구역은 11
개이다. 가장 단순하게 생각하면 다음과 같은 아이디어를 떠올릴 수 있다.
10개의 화살을 11개의 구역에 놓는 경우를 탐색해야 하는구나!
이렇게 될 경우 중복조합이므로 경우의 수는 11H10 = 184756
개가 된다. 충분히 탐색 가능한 범위이므로 바로 구현에 들어가도 좋다.
하지만 이는 불필요한 탐색까지 포함하고 있다. 문제를 잘 파악하면 라이언
이 점수별 맞춰야할 화살의 갯수는 정해져 있음을 알 수 있다. 해당 점수를 얻을 것이라면 어피치
가 맞춘 갯수보다 한 발을 더 맞추면 되고, 그렇지 않다면 아예 쏘지 않는 것이 최적일 것이다. 따라서 우리가 탐색해야할 것은 다음과 같다.
0 ~ 10점짜리 총 11개의 과녁 중 점수를 얻을 과녁 고르기
즉 하나의 점수당 점수를 얻을지 말지 2가지 선택지 뿐이다. 따라서 모든 경우의 수는 2^11 = 2048
개이고, 중복조합과 마찬가지로 완전탐색
이지만 경우의 수가 훨씬 적은 것을 알 수 있다.
이때 구현에 있어서 유의해야 할 조건들이 있다.
info
의i
번째 원소는 과녁의10 - i
점을 맞힌 화살 개수라이언
과어피치
모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도k
점을 가져가지 않음라이언
과어피치
의 과녁 점수 또는 총점이 동점일 때는어피치
의 승리라이언
이 어떻게 화살을 쏘든라이언
의 점수가어피치
의 점수보다 낮거나 같으면[-1]
을 return라이언
이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return
1~4번째 조건은 구현 상 사소한 조건이지만 마지막 조건의 경우 어려움을 느낄 수 있다. 화살을 마지막 한 발까지 알뜰하게 사용해야 최대 점수 차이를 갱신할 수 있는 경우라면 상관없겠지만 화살이 남는 경우에 대해 손을 써줘야한다. 이때 화살이 남았을 경우 0점 과녁에 전부 몰아주는 식으로 구현을 하면 문제의 조건을 만족시키는 경우의 수를 탐색 범위에 포함시킬 수 있다.
간단 후기
필자는 실제 코딩테스트 응시 때 본 문제에서 많은 시간을 허비했다. 하나의 점수당 얻을지 말지에 대해 최적으로 고른다는 점에서 DP
에 기반한 냅색 문제
임이 틀림없다 생각했다. 거기에 라이언
의 과녁 배열을 리턴해야 하므로 재귀
를 통해 DP
배열을 역추적까지 해야한다는 생각에 긴 장정을 예상하고 코드를 써내려갔다. 이렇게 꽤 오랜시간을 들여 제출했는데 전체 테스트케이스 중 2
개가 통과되질 않았다. 멘붕이 와서 뒷 문제들을 살짝 훑어보다가 너무 많은 시간을 들인 것이 아쉬워서 다시 돌아와 문제를 재차 읽어보았다. 그런데 n
의 범위가 최대 10으로 너무 작은 것이 눈에 띄었다. 그래서 부랴부랴 완전탐색
으로 코드를 고치니 통과할 수 있었다. 그 때의 풀이 코드를 저장해두진 않았어서 아직도 DP
풀이가 왜 오답이 나왔었는지는 모르겠다. 다만 완전탐색
문제가 하나씩은 꼭 출제된다는 점을 상기했더라면 더 빨리 풀 수 있지 않았을까 싶다.
전체 코드
1 |
|