볼링공 고르기

문제

N개의 볼링공을 같은 무게라도 번호가 다르면 서로 다른 공으로 간주할 때, 두 사람이 서로 다른 무게의 볼링공을 고를 수 있는 모든 경우의 수를 구하라.

 

 

아이디어

1. for, for 해서 모든 순열을 구한다.

2. 조합 - 같은 번호를 가진 볼링공 수

 

3. 기록을 통한 체크

입력 (1, 3, 2, 3, 2) - 출력 8

번호 : (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5)

무게 : (1, 3), (1, 2), (1, 3), (1, 2), (3, 2), (3, 2), (2, 3), (3, 2)

- 볼링공의 조합을 생각해보면 결과적으로는 번호가 다르고 무게가 달라야한다.

- 1. 번호를 고려해서 생각해보면 for 문 이외에는 생각이 나지 않는다.

(번호가 다른지 확인 후 무게 또한 다르면 count)

- 2. 무게로 따져보자. (번호는 모든 공이 다르기에 가능)

- 무게 조합을 보면 (1, 2), (1, 3), (2, 3) 이 있다. (순서가 바뀌어도 같은 경우의 수라는 것을 고려)

(공1 의 수 : 1개) * (공2의 수 : 2개) = 2개의 경우의 수 -> 무게가 1인 공의 수 * 무게가 1보다 큰 공의 수

(공1 의 수 : 1개) * (공3의 수 : 2개) = 2개의 경우의 수 -> 무게가 2인 공의 수 * 무게가 2보다 큰 공의 수

(공2 의 수 : 2개) * (공3의 수 : 2개) = 4개의 경우의 수 -> 무게가 3인 공의 수 * 무게가 3보다 큰 공의 수

 

 

 

정당성

"항상 특정 무게에 대해서 이보다 큰 무게와의 조합을 고르면, 번호도 다르고 무게도 다름을 만족한다 또한 똑같은 경우의 수를 고를 경우도 없어진다 ex (1, 2), (2, 1)"

 

 

코드

# for, for로 조합 구현
result = 0
for i in range(n):
    for j in range(i+1, n):
        if balls[i] != balls[j]:
            result += 1
print(result)



# 조합값 - 겹치는 공의 수
result = int(n1*(n1-1)/2)
count = 0
for i in range(n):
    if i+1 <= n-1:
        if balls[i] in balls[i+1:]:
            count += 1
print(result-count)



# 기록을 통한 구현
array = [0]*m
for i in balls:
    array[i] += 1
result = 0
for i in range(1, m+1):
    n -= array[i]
    result += array[i]*n
print(result)

n -= array[i]의 의미.

예를들어, 1부터 i가 출발을 할때, n -= array[i]는 자연스럽게 n보다 큰 공의 수를 의미한다.

총 공의 개수 n에서 자신의 개수를 빼기 때문이다.

 

 

 

시간 복잡도

1. O(N**2)

2. O(N**2)

3. O(N)