볼링공 고르기[이코테] 그리디

볼링공 고르기

 

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

 

입력조건 

  - 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다.

(1 <= N <= 1000, I <= M <= 10)

  - 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.

 

<나의 답안>  

# 볼링공 고르기 p.315
from itertools import combinations

if __name__ == '__main__':
    n, m = map(int, input().split())
    arr = list(map(int,input().split()))
    numArr = [0]*n
    for i in range(n):
        numArr[i] = i+1

    comArr = list(combinations(arr,2))
    result = 0
    for i in comArr:
        if i[0] != i[1]:
            result +=1
    print(result)

 

<나의 답안 해설>

 

위의 문제는 2사람이 볼링공을 고르는 경우의 수를 출력하면된다. 하지만, 한 가지 조건이 있다. 

2명의 사람은 서로 무게가 다른 볼링공을 골라야 한다. 

따라서 2명(2개의 수의조합)을 토대로 combination으로 순서 변경없는 조합의 수를 찾아냈다. 

그다음에 2개의 값이 같으면 for문에서 값을 더하지 않는 식으로 해결하였다. 

 

<정답>

# 볼링공 고르기 p.315
if __name__ == '__main__':
    n, m = map(int, input().split())
    data = list(map(int, input().split()))
    
    # 1부터 10까지의 무게를 담을 수 있는 리스트
    array = [0] * 11
    
    for x in data:
        # 각 무게에 해당하는 볼링공의 개수 카운트
        array[x] += 1
        
    result = 0
    # 1부터 m까지의 각 무게에 대하여 처리
    for i in range(1, m+1):
        n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
        result += array[i] * n # B가 선택하는 경우의 수와 곱하기
    
    print(result)

정답의 경우 정답을 보면 명쾌해 질 줄 알았는데 쉽지 않다고 느끼게 되는 것 같다.