[프로그래머스] 양궁대회 - python

문제 출처

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

프로그래머스

 

 

 

---

문제 풀이

알고리즘 문제는 풀어도 풀어도 어렵다. 꾸준히 문제 푸는 습관을 들여야 하는데 이게 참 어렵다.

 

필자는 처음에 knapsack을 이용해서 해결하고자 했다. 하지만 knapsack을 이용해 구하고자 쉽지 않았다. 먼저 knapsack은 기본적으로 제한된 cost내에서 최고의 value를 구하는 알고리즘이다. 따라서 10개의 화살을 이용해 최대 점수를 구한다고만 생각했고 충분히 구현 가능할 것이라고 생각했다. 모두 구현하고서 깨달았지만 해당 문제는 라이언의 최대 점수를 구하는 것이 아니라, 라이언과 어피치의 점수차이를 최대로 벌리는 것이다. 따라서 해당 방식을 이용해서 접근하자니 오랜 시간이 걸렸고 보다 복잡해졌다.

 

두번째로 생각한 방식은 모든 경우를 체크해보는 것이었다. 아마 itertool의 combinations_with_replacement를 사용해서 구현해볼까 하는 생각이 들었다. 하지만 이 경우에는 시간 복잡도가 꽤 높게 나올 것이다. 라이언과 어피치의 값의 차이를 최대로 만들기 위해서는 특정 점수 과녁을 어피치보다 많이 쏘거나, 아예 포기 하고 다른 과녁를 노려야한다. 하지만 중복 조합의 경우는 어피치가 쏜 곳에 작은 개수의 화살을 쏘는 경우도 포함되기에 무의미한 값들이 들어가는 경우가 많아진다. 따라서 비효율 적이라고 생각했다.

 

따라서 어떤 점수 과녁을 맞춰야 할지에 대한 목표가 있어야 한다. 목표로 하는 과녁은 어피치보다 1발 더 많이 쏘는 것이 좋다. 따라서 10짜리 어레이를 만들고 그 안에 0, 1을 통해 맞출 목표 과녁을 체크하면 된다. 하지만 필자는 비트 마스킹을 사용했다. 10개의 점수 과녁이 있기에 2^10 즉 1024개의 경우가 존재하며 해당 경우마다 10개 점수판을 모두 확인해야하기에 대략 10000 정도의 시간 복잡도가 필요로 한다.