[2022 KAKAO Blind Recruitment] Q4. 양궁 대회 (C++, Python, Java)

문제 링크

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

 

예상 난이도

G5

 

알고리즘 분류

시뮬레이션/그리디

 

풀이

먼저 시뮬레이션 풀이부터 설명드리면, 문제의 상황은 n발의 화살을 0에서 10점 사이의 값으로 정하면 되는 상황이고 값은 중복될 수 있으나 순서는 고려하지 않아도 되기 때문에 중복 조합임을 알 수 있습니다. 11개에서 중복을 허용해 n개를 뽑는 경우의 수는 n+10개에서 중복을 허용하지 않고 10개를 뽑는 경우의 수와 동일하기 때문에 최대 20 choose 10 = 184,756가지만 고려하면 됨을 알 수 있습니다.

 

b개에서 중복을 허용해 a개를 뽑는 경우의 수 = a+b-1개에서 중복을 허용하지 않고 b-1개를 뽑는 경우의 수라는 이 내용에 대해 간략하게 소개를 드리겠습니다.

 

3개의 원소 중에서 중복을 허용해 4개를 뽑는 모든 경우를 따지기 위해서는 지금 중간에 있는 이 그림과 같이 6개의 칸에서 2개의 칸막이를 선택해 구간을 3개로 나누면 됩니다. 기억이 안날 수 있지만 아마 관련된 내용을 고등학교 수학 시간에 배운 적이 있을거라 헷갈리면 중복 조합이라고 검색해서 관련된 정보를 확인해보세요.

 

이 중복 조합은 백트래킹을 이용해 구현할 수 있고, 칸막이를 뽑는다는 아이디어를 그대로 가져와 C++에서는 next_permutation을 이용해도 되고, Python에서는 그냥 combinations_with_replacement 함수 자체가 중복 조합 상황을 그대로 흉내내주기 때문에 구현이 아주 편합니다. 자바에서는 직접 백트래킹으로 구현해야 합니다.

next_permutation으로 이용해 중복 조합을 처리했고 백트래킹으로 하는 방법도 주석으로 달아두었습니다. 중복이 허용되지 않는 조합에서는 next_permutation이 훨씬 더 간단하기 때문에 next_permutation의 사용을 권장하지만 중복 조합에서는 둘의 난이도가 비슷해서 백트래킹 혹은 next_permutation 중 편한 것을 사용하면 됩니다.

 

두 번째 풀이는 그리디 풀이입니다. 저는 사실 처음 이 문제를 풀 때 그리디 풀이로 바로 접근을 했습니다. 이 풀이를 착안하고 나서 문제가 괜찮다고 생각을 했었는데 나중에 시뮬레이션으로도 가능하다는걸 깨닫고 살짝 허탈했었습니다. 만약 n이 더 컸다면 시뮬레이션 풀이는 시간 초과가 발생하고 그리디 풀이만 통과되었겠지만 지금의 제한 조건에서는 두 풀이 모두 통과됩니다.

 

아무튼 중복 조합으로 모든 가능한 과녁 점수의 조합을 확인하는 대신, 라이언이 가져갈 과녁 점수의 목록을 고정하고 나면 라이언의 n발의 화살이 어떻게 구성되어야 하는지가 바로 정해집니다.

 

예를 들어 라이언이 10점, 6점, 3점에서 이기기로 결심했다면 10점, 6점, 3점에서는 어피치보다 딱 1개만 더 맞추고 나머지 점수는 전부 0개만 맞추면 됩니다. 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지일 경우 가장 낮은 더 많이 맞힌 경우를 return하라는 조건을 만족시키기 위해서는 남은 화살을 전부 0점에 몰아주어야 합니다.

 

이와 같이 2¹⁰개의 가능성에 대해서만 전부 따지면 됩니다. 실제 구현을 할 때 이렇게 점수를 고정했을 때 화살을 n개보다 더 많이 써야하는 경우, 라이언의 점수가 어피치의 점수 이하인 경우 등을 잘 신경써야 합니다.

 

코드(C++, 시뮬레이션)

 

next_permutation을 이용해 코드를 작성했고, 그와 별개로 백트래킹을 이용하는 코드도 주석으로 두었으니 궁금하시면 확인해보세요.

 

코드(C++, 그리디)

 

코드(Python, 시뮬레이션)

파이썬에서는 combinations_with_replacement 함수의 존재로 인해 구현이 상당히 쉬워집니다. 굳이 백트래킹으로 구현할 필요는 없습니다.

 

코드(Python, 그리디)

 

코드(Java, 시뮬레이션)

자바에서는 중복 조합을 백트래킹으로 직접 구현해야 합니다. 

 

코드(Java, 그리디)