[이코테] 그리디 - 볼링공 고르기 with 파이썬

1. 문제 : 볼링공 고르기

• N, M , 볼링공의 수 , 무게 종류의 수 가 들어온다.
• 공백을 둔 N개의 볼링공의 무게가 들어온다.
• 두 사람이 볼링공을 고르는 경우의 수를 구하라.

입력 조건

• N : 볼링공의 수 (1<= N <=1000), M : 볼링공의 무게 ( 1<= M <=10) 입력
• 공백을 둔 무게 K (1<= K <= M) 입력

출력 조건

• 두 사람이 볼링공을 고르는 조건의 수

입력 예시

5 3
1 3 2 3 2

출력 예시

8

2-1. 아이디어 (my version)

• 앞 사람이 고른 공과 다르면, 경우의 수를 올린다.
• O(N^2) , max 1000 이기 때문에, 1000000번 연산으로 시간 초과는 하지 않을 듯하다.

2-2. 저자 아이디어

• 공의 무게를 개수를 다른 리스트에 저장한다. (자연적으로 순차적으로 보게 된다)
• 공의 무게를 저장한 리스트를 활용해서 A의 선택의 수, B의 선택 (A가 선택한 경우 제외)를 곱하면서 결과에 적산한다.

3-1. 예제 코드 (my version)

# 입력
N, M = map(int, input().split())
balls = list(map(int, input().split()))

cnt = 0  # 경우의 수 저장 
for i in range(len(balls)-1):         # A 경우 
    for j in range(i+1, len(balls)):  # B 경우 
        if balls[i] != balls[j]:      # A와 B가 다르면
            cnt += 1                  # 경우의 수 올린다. 
            
print(cnt)

3-2. 예제 코드 (저자 버전)

# 입력
N, M = map(int, input().split())
balls = list(map(int, input().split()))
# 공 무게 리스트 
weights = [0]*11       # 1부터 사용하려고

for ball in balls:     
    weights[ball] += 1 # 공 무게의 수 모으기

result = 0
for i in range(M+1):
    N -= weights[i]    # A가 선택한 경우 제외 
    result += weights[i] * N  # A가 선택한 경우 * B가 선택한 경우
    
print(result)

4. 배운점

• 중복된 값이 있는 상태에서 조합의 개수를 구하는 방법에 대해서 배웠다.

참고

• 이것이 취업을 위한 코딩 테스트다 with 파이썬