문제 출처
- 이것이 취업을 위한 코딩테스트다 with 파이썬
- Chapter 11 - 그리디 5. 볼링공 고르기
제한
- 시간 제한 : 1 초
- 메모리 제한 : 128 MB
문제
- A, B 두 사람이 볼링을 치고 있다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어진다.(1 <= N <= 1,000, 1 <= M <= 10)
- 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어진다.(1 <= K <= M)
출력
- 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력한다.
👀 풀이
- 처음에는 조합을 구하는 재귀함수를 구현해서 경우의 수를 세는 등 이상하게 코드를 짜다가 안 되서 해설을 봤다.
- 나의 접근법은 완전히 잘못 되었었다…
- 같은 무게의 공을 고를 수 없기 때문에 A가 고르는 공의 무게에 따라 B가 고를 수 있는 공의 종류가 달라진다. 게다가 순열이 아닌 조합을 고르는 것이기 때문에 중복되는 조합은 제외시켜가며 경우의 수를 구해야 한다.
- 그렇기 때문에 입력받은 공의 무게가 각각 몇 개인지 기록해 둔 다음 (A가 고를 수 있는 특정 공의 개수 * 특정 공을 제외한 B가 고를 수 있는 나머지 공의 개수)들을 더해주어야 한다.
코드
