Q05 볼링공 고르기

domybest·2021년 4월 9일
0

실전 문제

목록 보기
5/34

문제 : 이것이 코딩테스트다 교재 Q05번 실전문제
풀이 코드

알고리즘

2명이 무게가 서로 다른 공을 선정하는 경우의 수를 구하는 문제이다. 책에서 소개하는 방식과는 다르지만 나는 수학적으로 문제를 해결했다.
2명이 서로 다른 공을 선택하는 조합의 수 (공의 개수)C(2) 에서 같은 무게를 가지는 공의 수들의 조합을 빼면 된다. 즉 1 2 2 3 3 이라는 무게의 공들이 주어졌을 때
5C2 - 2C2(무게가 2인 공을 2개 뽑는 경우의 수) - 2C2(무게가 3인 공을 2개 뽑는 경우의 수) = 8 가지의 경우의 수가 정답이다. 이 식을 그대로 적용하면 문제는 해결된다.

책에서 소개한 방식에 대해서도 살펴보자. A가 특정한 무게의 볼링공을 선택했을 때 B가 선택하는 경우를 차례대로 계산하여 문제를 해결한다.

A가 무게 1인 공을 선택한다면 
무게가 1인 공의 개수(1개) * B가 선택하는 경우의 수(2, 2, 3, 3중 하나이니까 4개)
A가 무게 2인 공을 선택한다면
무게가 2인 공의 개수(2개) * B가 선택하는 경우의 수(3, 3중 하나이니까 2개, 1을 뽑는건 앞에서 했으니 경우의 수로 치지 않음)
A가 무게 3인 공을 선택한다면
무게가 3인 공의 개수(2개) * B가 선택하는 경우의 수(없음) 

코드로 알고리즘 핵심 부분을 살펴보자.

for i in range(1, m  + 1):
	n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    	result += array[i] * n # B가 선택하는 경우의 수와 곱하기

공의 선택 '조합' 이기 때문에 B가 선택할 수 있는 경우의 수는 원래보다 더 줄어들게 된다. 그래서 n(전체 공의 개수) 에서 계속 무게가 i인 볼링공의 개수를 빼 나간다.

둘 다 효율성은 O(m)이다. m + 1 크기의 배열을 1부터 m의 index 까지 반복하기 때문이다.

profile
기억할 때 까지 반복!

0개의 댓글