볼링공 고르기

INGBEEN·2021년 11월 1일

python 그리디 알고리즘

알고리즘 문제

목록 보기

6/20

문제 설명

두 사람이 볼링장에서 볼링공을 고르려 한다. 각 볼링공은 번호와 무게가 있는데, 두 사람이 고른 볼링공의 무게가 서로 다르게 고르려고 할 때 경우의 수는 총 몇 가지인가?

<제한 사항>
시간 제한 : 1 sec
메모리 제한 : 128 MB

<입력>
첫 째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 주어진다.
(1 <= N <= 1000)
(1 <= M <= 10)

두번 째 줄에는 N게의 볼링공의 무게가 공백으로 구분되어 주어진다. 이 때 각 볼링공의 번호는 순서대로 0 ~ n-1까지이다.

<출력>
두 사람이 볼링공을 고르는 경우의 수를 출력한다.

<예시>
5 3
1 3 2 3 2
8

8 5
1 5 4 3 2 4 5 2
25

나의 풀이

n = 1000 -> 성공
무게가 커봤자 10이니까 dictionary형태로 각 무게의 볼링공 개수를 저장한 다음,
result =
dic[1] * (dic[2] + ... + dic[m])
+ dic[2] * (dic[3] + ... + dic[m])
+ ...
+ dic[m-1] * dic[m]
이런 식으로 생각했다.

n, m = map(int, input().split())
data = list(map(int, input().split()))

dic = dict()
for i in range(1, m+1):
    dic[i] = 0
for i in range(n):
    dic[data[i]] += 1
result = 0
for i in range(1, m+1):
    temp = 0
    for j in range(i+1, m+1):
        temp += dic[j]
    result += dic[i] * temp
print(result)

책 풀이

책도 비슷한 원리인데, dictionary 대신 list를 썼다. 더 깔끔해 보인다.

n, m = map(int, input().split())
data = list(map(int, input().split()))

array = [0] * 11
for x in data:
    array[x] += 1

result = 0
for i in range(1, m+1):
    n -= array[i]
    result += array[i] * n

print(result)