[이코테] 4일차 Greedy _ 만들 수 없는 금액, 볼링공 고르기

🏆Today Code Test

---

[1] 만들 수 없는 금액 🔴

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요

입력 조건

• 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주저집니다. (1 ≤ N ≤ 1,000)
• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수 입니다.

출력 조건

• 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

🛠Problem Approach

✅ 할 수 있는 모든 조합을 구함 → 조합 안 수를 순서대로 체크함 → 체크 안되는 수 출력

🔑Solution

#25'
n = int(input())
coins = list(map(int, input().split()))[:n]
coins.sort()

per = set(coins)
for i in range(len(coins)):
  make = coins[i]
  for j in range(i+1,len(coins)):
    make += coins[j]
    per.add(make)

cnt = 1

while True:
  if cnt not in per:
    print(cnt)
    break
  cnt += 1

# 위의 코드는 틀림
예시 ) input : 1 2 3 9 output : 7이 답

내 코드는 4가 나옴; 합이 아닌 모든 조합을 찾지 못 하기 때문

 

🎈구조 이해 하기

step 0 1원 부터 확인하기 위해 target = 1
step 1 target이 있다면, target을 1 + 1로 업데이트 (→ 2원까지 모든 금액을 만들 수 있다)
step 2 다음 동전으로 현재 target을 만족 시킬 수 있는지 확인(현재 동전 값보다 target이 작아야 한다) → 가능하다면,
target update
step 3 계속 반복하다가, 동전 값이 target보다 크다면, 현재 target은 만들 수 없다는 말이므로 종료
step 4 target이 만들 수 없는 금액이 된다.

n = int(input())
data = list(map(int, input().split())
data.sort()

target = 1
for x in data:
	if target < x: 
		break
	target += x

print target

[2] 볼링공 고르기 🟢

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

1. N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르느 경우의 수를 구하는 프로그램을 작성하세요.

입력 조건

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

출력 조건

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

🛠Problem Approach

✅ 조합 경우의 수 출력하기 → 조합 경우의 수 중에서 같은 무게를 가진 애 빼줘야 → 조건문으로 걸기 → 경우의 수니까 횟수만 세고, 저장소 낭비하지 말기!

🔑Solution

# 10'21"
n, m = map(int, input().split())
weights = list(map(int, input().split()))[:n]

cur = 0
cnt = 0

for i in range(len(weights)):
   cur = weights[i]
   for j in range(i+1,len(weights)):
     if cur != weights[j]:
       cnt += 1

print(cnt)

$O(n)$으로 풀기

n, m = map(int, input().split())
data = list(map(int, input().split()))

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

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)