📍 이것이 코딩테스트다(나동빈) - part3.알고리즘 유형별 기출문제 를 풀고 기록했습니다.

1. 만들 수 없는 금액

• N개의 동전을 가지고 있다. 이 때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값은?
• 첫째 줄에 동전의 개수를 나타내는 양의 정수 N이 입력됨.(1<=N<=1,000)
• 둘째 줄에 각 동전의 화폐단위가 주어짐. (각 화폐 단위는 1,000,000 이하의 자연수)
• 예를 들어 N = 5, 화폐단위 = [3, 2, 1, 1, 9]이면 8을 출력

1. 내 답안

• ⏳ 2시간 넘게 소요
• 부분집합 알고리즘 검색해서 가능한 모든 금액 계산한 후
• for i in range(1, max(list))로 일일이 대조함.

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


data.sort()

# 만들 수 없는 금액 구하는 함수
def cannot():
  # 1이 포함되어있지 않으면 만들 수 없는 금액은 1
  if min(data) < 1:
    return 1

  # 부분집합마다 합 구하기
  list = []
  for i in range(1<<n): #range(2^n)
    s = 0
    for j in range(n): #j는 data에서 인덱스
      if i & (1<<j):
        # A & B : A와 B의 2진수 형태에서 공통된 값을 가져와 10진수로 변환
        # 공통된 값이 없다면 0이 나옴.
        s += data[j]
    list.append(s)
  
  # list의 최댓값까지 확인
  for i in range(1, max(list)):
    if i not in list:
      return i

print(cannot())

1.2 책 답안

• 예를 들어 [1, 2, 3] 이 있다고 할 때 총 6까지 만들 수 있음

  1
  2
  3
  4 (= 1+3)
  5 (= 2+3)
  6 (= 1+2+3)

• 여기에 5원짜리 동전이 추가되면

  0 +5 =5
  1 +5 =6
  2 +5 =7
  3 +5 =8
  4 +5 =9
  5 +5 =10
  6 +5 =11

  • 1부터 11까지 만들 수 있음.
  • 만약 5원이 아니라 8원이 추가된다면? : 1~6, 8~13을 만들 수 있음.

• 책 답안

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)

target=1

• '1을 만들 수 있는지 부터' 시작. 차례대로 target 금액을 늘릴건데 어떻게 늘릴거냐면

for x in data

• 오름차순 정렬된 화폐단위(data)를 차례대로 확인하면서 target 금액을 늘림

현재 화폐단위 = x, target=N 인 상황은

• '이전' 화폐단위들로 1,2,...,(N-1)까지 만들 수 있다는 것을 확인하고 target=N으로 업데이트 한 상황
• 그래서 여기에 x를 추가로 이용한다면
• {1,2,...,(N-1)} or {x,1+x, 2+x, ..., (N-1)+x} 을 만들 수 있다.

if target < x:

• 이 때, x<=N 이면, 1부터 (N-1)+x까지 만들 수 있는 셈.
• 이와 반대인 N<x이면 N(=target)은 만들지 못함. -> break하고 '만들 수 없는 금액 중 최솟값'으로 N을 출력

target+=x

• x<=N 이면, 1부터 (N-1)+x까지 만들 수 있는 셈이므로 target은 여기에 1을 더한 N+x 로 갱신

✅ 실수 주의

• target < x 에서 break 안하면 1

• 1~ sum(data)까지 모두 만들 수 있는 경우 result = 0 으로 그대로 나옴.

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

result = 0
target = 1 
for x in data:
  if target >= x:
    target += x
  else:
    result = target

print(result )