그리디 알고리즘 : 볼링공 고르기 - 파이썬 (python)

- 입력 조건

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

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

- 출력 조건

첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력합니다.

 

테스트케이스 1) 5 3 / 1 3 2 3 2 -> 8

테스트케이스 2) 8 5 / 1 5 4 3 2 4 5 2 -> 25

 

* 방법1

직접 풀이한 방식이며 이중for문을 이용하여 (1번, 2번), (1번, 3번), (1번, 4번) ... 을 차례대로 비교하고 두 값이 같지 않으면 result 값을 1씩 증가시킨다. 

#방법1
n, m = map(int, input().split()) #n: 볼링공의 개수 m: 볼링공의 최대 무게
data = list(map(int, input().split())) #n개의 공의 무게
result = 0

for i in range(n):
    for j in range(i, n):
        if data[i] != data[j]:
            result += 1

print(result)

* 방법2

이 문제를 효과적으로 해결하기 위해서는, 먼저 무게마다 볼링공이 몇 개 있는지를 계산해야 한다.

테스트케이스 1의 경우 무게가 1인 볼링공: 1개, 무게가 2인 볼링공: 2개, 무게가 3인 볼링공: 2개

이 때 A가 특정한 무게의 볼링공을 선택했을 때, A를 기준으로 무게가 낮은 볼링공부터 무게가 높은 볼링공까지 순서대로 하나씩 확인을 한다고 했을 때 다음과 같다.

 

(1) A가 무게 1인 공을 선택할 때의 경우의 수는

1 (무게가 1인 공의 개수) x 4 (B가 선택하는 경우의 수) = 4가지 경우가 있다.

(2) A가 무게 2인 공을 선택할 때의 경우의 수는

2 (무게가 2인 공의 개수) x 2 (B가 선택하는 경우의 수) = 4가지 경우가 있다.

(3) A가 무게 3인 공을 선택할 때의 경우의 수는

2 (무게가 3인 공의 개수) x 0 (B가 선택하는 경우의 수) = 0가지 경우가 있다.

 

따라서 가능한 경우의 수는 총 8가지이다.

# 방법2
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)

 

 

 

github.com/501501/codingTest/commit/a627e765a56dd7f61fab899625e9295a1e6ed15e

#11-05 · 501501/codingTest@a627e76