[이.취.코] Chap 11. 그리디 - Q5. 볼링공 고르기

@mildsalmon·2021-09-08 08:16

1. 볼링공 고르기

난이도
- 하
풀이 시간
- 30분
시간 제한
- 1초
메모리 제한
- 128 MB
출처
- 2019 SW 마에스트로 입학 테스트

A. 문제

A, B 두 사람이 볼링을 치고 있다.
두 사람은 서로 무게가 다른 볼링공을 고르려고 한다.
볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다.
볼링공의 무게는 1~M까지의 자연수 형태로 존재한다.

a. 예를 들면.

N = 5, M = 3이며 무게가 1, 3, 2, 3, 2일 때 각 공의 번호가 차례대로 1, 2, 3, 4, 5번으로 부여된다. 이때 두 사람이 고를 수 있는 볼링공의 조합을 구하면, 아래와 같다.

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

두 사람이 공을 고를 수 있는 경우의 수는 8가지이다.

b. 입력 조건

첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어진다
- 1 <= N <= 1,000
- 1 <= M <= 10
둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어진다.
- 1 <= K <= M

c. 출력 조건

첫번째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력하라.

d. 테스트 케이스

입력 예시
```
5 3
1 3 2 3 2
```
```
8 5
1 5 4 3 2 4 5 2
```
출력 예시
```
8
```
```
25
```

B. 내 답안

a. 1차 시도 (내가 생각해본 반례에서 틀림)


from itertools import combinations  
  
n, m = list(map(int, input().split()))  
array = list(map(int, input().split()))  
count_sort = [0] * (m+1)  
result = 0  
  
for i in array:  
    count_sort[i] += 1  
  
for i in range(1, len(count_sort)):  
    if count_sort[i] > 0:  
        count_sort[i] -= 1  
print(count_sort)  
for i in count_sort:  
    if i < 2:  
        result += i  
    else:  
        result *= i  
print(result)  
result = len(list(combinations(array, 2))) - result  
  
print(result)

b. 2차 시도 (통과)


from itertools import combinations  
  
n, m = list(map(int, input().split()))  
array = list(map(int, input().split()))  
result = 0

combi = list(combinations(array, 2))  
# print(combi)  
  
answer = len(combi)  
  
for i in combi:  
   A, B = i  
   if A == B:  
       answer -= 1  
  
print(answer)

c. 반례


# 반례  

# 5 3  
# 1 1 1 2 3 

# 10 8  
# 1 1 2 3 3 8 4 8 8 2

a. 회고

풀이

조합이라는 단어가 있길래, Combination이 떠올랐다.
하지만, 기존 Combination에서 조건이 하나 더 추가된다.
- 두 사람이 고른 볼링공의 무게가 같으면 안된다.
즉, N개의 볼링공의 조합을 구한다. -> 구한 조합에서 볼링공의 무게가 같은 경우를 제외한다.
- list의 pop() 메소드를 사용하려다가, 쓸데없이 시간 복잡도가 증가할 것으로 생각하여, 간단하게 len()을 사용하였다.
  - list메소드의 시간복잡도는 len()은 O(1), pop(i)는 O(N)이다.