[이것이 코딩 테스트다 with Python] Chapter 11. 그리디 - 볼링공 고르기

< 볼링공 고르기>

 

💬 문제 설명

A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀있고

....

 

입력	출력
5   3 2 1 1 9	8

💬 입력 조건

• 첫째 줄에 볼링공의 개수 N ( 1 ≤ N ≤ 1,000 ) , 공의 최대 무게 M ( 1 ≤ M ≤ 10 ) 이 공백으로 구분되어 각각 자연수 형태로 주어짐. 
• 둘째 줄에는 각 볼링공의 무게 K ( 1 ≤ N ≤ M ) 가 공백으로 구분되어 순서대로 자연수 형태로 주어짐.

💬 출력 조건

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

---

✍ 문제요약

A, B 두 사람이 볼링을 치려는데, 볼링공의 종류가 무게(무게가 같아도 다른 종류로 취급)와 함께 주어진다. 이 때 A, B가 다른 무게를 선택하여 볼링을 치는 경우의 수를 구하라.

---

✅  문제 풀이 

1️⃣ 2중 for문

• 볼링공 리스트에서 A가 먼저 공 고르고, B가 그 뒤에 공을 고른다.
• 이렇게 고른 공의 무게가 다를 때의 갯수를 세린다.
• 아주 단순한 사고로 풀 수 있다.

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

count = 0
for i in range(N-1):
    for j in range(i+1,N):
        if balls[i] != balls[j] : count+=1
print(count)

 

2️⃣ 1중 for문

• 볼링공 무게의 리스트를 하나 만든다.
• 무게에 대한 1중 for문을 돌린다.
• 해당 무게를 A가 선택했다고 한다면
• N -= array[w] 전체 수 N에서 해당 무게리스트의 값을 빼고
• count += array[w] * N 해당 무게 리스트에 곱하면 B가 고를 수 있는 수가 된다.

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

array = [0] * 11   # 1부터 10까지 무게를 담는 리스트

for w in balls:
	array[w] += 1
   
count = 0
for w in range(1, M + 1): 
	N -= array[w]           # A가 선택하는 수 제외
    count += array[w] * N   # 무게가 w인 공의 개수 * B가 선택하는 경우의 수