[그리디 9] 볼링공 고르기
책에서 나온 풀이는 꼭 기억하기. 하나를 기준으로 삼고, 다른 하나를 선택할 때에 사용자 정의 리스트를 만들어서 이용할 수 있다. (문제의 조건인 1 <= M <= 10 이용)
미니 예제 1
1. 문제 설명하기.
A, B 두 사람이 있는데, 서로 무게가 다른 볼링공을 고르려고 한다.
N은 볼링공의 개수이고, M은 볼링공의 무게이다. (1 ~ M 까지의 자연수 형태)
2. 문제 해결하기.
나는 조건에 만족하는 경우에 +1 처리하는 방식으로 구하고자 한다. count라는 변수를 지정하여 0이라고 두고, 여기서 조건에 해당할 때마다 +1 처리를 해준다.
여기서 주의할 점은 인덱스를 2개를 이용해야 된다는 점이다. (조합의 개수를 구할 때 인덱스가 2개가 필요하다.) 기준이 되는 인덱스와 그 다음 인덱스가 필요하기에 중첩 반복문을 이용한다.
즉, 이 예제에서는
# 기준이 되는 인덱스, 그 다음 인덱스들
0 -> [1, 2, 3, 4]
1 -> [2, 3, 4]
2 -> [3, 4]
3 -> [4]Step 1. 기준이 되는 인덱스 반복문을 돌린다.
Step 2. 기준이 되는 인덱스 다음 인덱스들을 반복문으로 돌린다.
Step 3. A, B의 무게가 같은 경우는 넘긴다.
Step 4. A, B의 무게가 다른 경우는 +1 처리한다.
# 미니 예제 1 : N=5, M=3
N=5
M=3
count=0
weight=[1,3,2,3,2]
for index in range(N-1): # 기준이 되는 인덱스
# print(index)
for idx in range(index+1, N): # 그 다음 인덱스
# print(idx)
# print("--")
if weight[index] == weight[idx]: # 무게가 같으면 넘기기.
continue
count+=1 # 무게 다른 경우는 +1 처리하기.
print(count) 미니 예제 2
1. 문제 설명하기.
A, B 두 사람이 있는데, 서로 무게가 다른 볼링공을 고르려고 한다.
N은 볼링공의 개수이고, M은 볼링공의 무게이다. (1 ~ M 까지의 자연수 형태)
2. 문제 해결하기.
나는 조건에 만족하는 경우에 +1 처리하는 방식으로 구하고자 한다. count라는 변수를 지정하여 0이라고 두고, 여기서 조건에 해당할 때마다 +1 처리를 해준다.
여기서 주의할 점은 인덱스를 2개를 이용해야 된다는 점이다. (조합의 개수를 구할 때 인덱스가 2개가 필요하다.) 기준이 되는 인덱스와 그 다음 인덱스가 필요하기에 중첩 반복문을 이용한다.
즉, 이 예제에서는
# 기준이 되는 인덱스, 그 다음 인덱스들
0 -> [1, 2, 3, 4, 5, 6, 7]
1 -> [2, 3, 4, 5, 6 ,7]
2 -> [3, 4, 5, 6 ,7]
.
.
.
6 -> [7]Step 1. 기준이 되는 인덱스 반복문을 돌린다.
Step 2. 기준이 되는 인덱스 다음 인덱스들을 반복문으로 돌린다.
Step 3. A, B의 무게가 같은 경우는 넘긴다.
Step 4. A, B의 무게가 다른 경우는 +1 처리한다.
# 미니 예제 2 : N=8, M=5
N=8
M=5
count=0
weight=[1,5,4,3,2,4,5,2]
for index in range(N-1):
# print(index)
for idx in range(index+1, N):
# print(idx)
# print("--")
if weight[index] == weight[idx]:
continue
count+=1
print(count) 최적의 일반화
1. 문제 설명하기.
위와 동일하다. 위와 다른 점은 데이터를 직접 받는다는 점이다. N, M은 같이 받고, 공의 무게인 weight는 리스트의 형태로 받았다.
2. 문제 해결하기.
# 최적의 일반화
N, M=map(int, input().split())
weight=list(map(int, input().split()))
count=0
for index in range(N-1):
# print(index)
for idx in range(index+1, N):
# print(idx)
# print("--")
if weight[index] == weight[idx]:
continue
count+=1
print(count) 3. 책에 나와있는 최적의 일반화
책에서는 볼링공의 무게가 1 ~ 10임을 이용한다. (모든 조건 이용)
| 기준 | 나의 풀이 | 책의 풀이 |
|---|---|---|
| 모든 경우의 수 구하기. | 조건에 맞으면 더하기. | (A의 선택) x (B의 선택) |
| 무게 나열하기. | 중첩 반목문 이용하기. | (정렬된) 무게 리스트 이용하기. |
일단 미니 예제를 통하여 풀어보자. N=5이고 M=3이다. 볼링공의 무게는 [1, 2, 2, 3, 3] 이다.
Step 1. 0으로 채워진 리스트 만들기.
Step 2. 정렬된 무게로 채워진 리스트 만들기.
Step 3. A를 기준으로 잡고, B의 경우의 수 구하기.
Step 4. (A 기준) x (B의 경우의 수)를 구하고자 하는 값에 더해주기.
# 책에 나와있는 일반화
N, M=5, 2 # 볼링공의 개수, 최대 무게
data=[1,2,2,3,3]
## Step 1.
array=[0]*11 # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 0 ~ 10까지 해당하는 볼링공의 무게
## Step 2.
for x in data:
array[x]+=1
print(array)
## Step 3.
result=0
for i in range(1, M+1): # A 기준
N-=array[i] # B 경우의 수
# print(N)
## Step 4.
result+=array[i]*N
print(result)N,M=map(int, input().split())
data=list(map(int, input().split()))
result=0
## Step 1.
array=[0]*11 # 0 ~ 10까지 해당하는 볼링공의 무게
## Step 2.
for i in data:
array[i]+=1
print(array)
## Step 3,4.
for i in range(1, M+1): # A 기준
N-=array[i]
result+=N*array[i]
print(result)