백준 2295번: 동전 2 (python)

문제

• https://www.acmicpc.net/problem/2294
• 전체 부분 집합들을 탐색하는 데 너비 우선 탐색 적용하기 (최단 경로 찾기)

기록 포인트

• 전체 부분 집합 탐색 과제를 너비 우선 탐색 방식으로 구성하는 과정
  • 이 문제는 조합 가능한 동전의 구성들(전체 부분 집합) 중 조건을 충족하는 부분 집합을 탐색하는 과제임
  • 목표를 달성하기 위해 더 작은 하위의 문제로 나누어 해결하며, 그 과정에서 중복된 문제가 등장하면 기록된 내용을 활용함
  • 목표값(K)를 만들기 위해 더 작은 목표값(K - coin1, K - coin2, ...)들로 만들어 해결을 하며, 이 과정에서 중복된 값이 등장하면 탐색에서 제외시킴
  • 아래의 예시는, 아래와 같이 이해할 수 있음
    • F(15)
    • = 1 + F(13) = 1 + F(8)
    • = 1 + (1 + F(11)) = 1 + (1 + F(6)) = 1 + (1 + F(1))
    • ...
• 이 문제가 최소 경로를 탐색하는 과정이었다는 점 이해하기
  • 이 과제의 목표는 사용한 동전 개수를 최소화하여 목표값을 완성하는 것이며, 이를 목표 지점까지 도달하는 최단 거리를 찾는 것으로 볼 수 있음

접근 방식

• BFS 방식으로 탐색
  • 완성시켜야 하는 값을 frontier(큐)에 넣어 탐색 시작
  • 각 문제를 해당 문제에서 파생 가능한 더 작은 문제로 나누어 큐에 다시 추가
    • 완성시켜야 하는 값(k): 정점(v)의 역할
    • 활용 가능한 동전(coin): 특정 문제(v1)를 하위 문제(v2)와 연결하는 간선(edge)의 역할
  • 이 때, 이미 발견한 정점(해결되었거나 큐에 남아 있는 하위 문제)는 탐색에서 제외시킴
• [예시] 2개의 동전 2와 7을 조합해서 15를 완성하기 (첨부 이미지 참고)
  • 이 때, 12번째 탐색으로 완성된 조합을 찾고난 뒤에는 추가 탐색 필요 없음
    - 우리의 목표는 동전을 최소 개수로 사용하는 것
    - BFS 방식으로 탐색 과정에서 더 적은 개수의 동전을 사용한 경우의 수를 모두 지나왔기 왔기 때문에, 답을 찾은 시점에는 더 적은 동전을 사용한 답은 없음
    

제출 답안

최종 답안

• 남은 값(v1)에서 동전(coin)을 하나 크기만큼 감소시킴
• 앞서 지나간 숫자는 추가로 탐색하지 않음
• 답을 찾은 시점에서 탐색 종료

import sys
from collections import deque

N, K = tuple(map(int, sys.stdin.readline().split()))
coins = []
for _ in range(N):
    coins.append(int(sys.stdin.readline()))
# 작은 값부터 확인 가능하도록 오름차순 정렬
coins.sort()

# 초기값 설정
# 동전들 중 목표 금액과 일치하는 값이 있는지 확인하여 조기 종료
if K in coins:
    min_count = 1
    frontier = []
else:
    min_count = -1
    frontier = deque([(K, 0)])

# 하위 문제로 분할 및 기록 누적하기
# - 너비 우선 탐색 과정에서 이미 지나간 숫자가 나중에 다시 등장하는 경우,
# - 해당 숫자까지 도달하는데까지의 누적 동전 수는 크고 남은 경로는 동일할 것이기 때문에
# - 결국 누적 동전 수가 최소가 될 수 없으며, 추가 탐색할 필요가 없음
parent = {K: None}
while min_count < 0 and frontier:
    # 남은 금액 v1, 누적 동전 수 cnt1
    v1, cnt1 = frontier.popleft()
    # 사용 가능한 동전들 하나씩 확인
    for coin in coins:
        # 남은 금액에서 동전 값만큼 빼서 새로운 값 구성
        # 누적 동전 수에 1 추가
        v2, cnt2 = v1 - coin, cnt1 + 1
        # 이미 탐색한 금액인 경우, 다음 동전으로 이동
        if v2 in parent:
            continue
        # 남은 금액이 음수인 경우, 다음 동전도 확인할 필요 없으므로 종료
        if v2 < 0:
            break
        # 남은 금액이 0인 경우, 조합 완성이며 다음 동전은 음수가 나올 것이므로 종료
        elif v2 == 0:
            min_count = cnt2
            break
        # 남은 금액이 양수인 경우, 추가 분할을 위해 큐에 추가
        else:
            # 중복 탐색을 막기 위해 parent에 추가
            parent[v2] = v1
            frontier.append((v2, cnt2))

print(min_count)

1차 답안 (오답)

• 남은 값(v1)에서 동전(coin)을 하나씩 빼지 않고, 가능한 전체를 빼버렸음
  • 다음 노드의 값(v2)는 v1%coin로 설정
  • 다음 누적 동전 수는 기존 값에 v1//coin을 더한 값으로 설정
  • 반례: 2개의 동전 [2, 7]을 사용해 15 만들기
    • 15에서 동전 2를 최대(7개)로 빼면 1이 남아 구성 실패
    • 15에서 동전 7을 최대(2개)로 빼면 1이 남아 구성 실패
    • 허나, 동전 2를 4개, 동전 7을 1개 사용하면 15 구성 가능

import sys
from collections import deque

N, K = tuple(map(int, sys.stdin.readline().split()))
coins = []
for _ in range(N):
    coins.append(int(sys.stdin.readline()))
# 작은 값부터 확인 가능하도록 오름차순 정렬
coins.sort()

# 사용 동전의 최대 개수 초기 설정
min_count = K 
# 동전들 중 목표 금액과 일치하는 값이 있는지 확인하여 조기 종료
if K in coins:
    min_count = 1
    frontier = []
else:
    # (목표 금액, 누적 동전 수)
    frontier = deque([(K, 0)])

# 동전 분할하기
# 분할 성공 여부 초기화
success = False
while frontier:
    # 남은 금액 v1, 누적 동전 수 cnt1
    v1, cnt1 = frontier.popleft()
    # 사용 가능한 동전들 하나씩 확인
    for coin in coins:
        # 남은 금액보다 동전 값이 크다면 분할 불가능하며, 다음 동전도 확인할 필요 없으므로 종료
        if coin > v1:
            break
        # 남은 금액보다 동전 값이 작거나 같으면 분할 
        # 남은 금액은 동전 값으로 나눈 나머지
        v2 = v1 % coin
        # 누적 동전 수는 남은 금액을 동전 값으로 나눈 몫을 기존 개수에 추가한 값
        cnt2 = cnt1 + v1//coin 
        # 만약 남은 금액이 없다면, 조합 완성
        if v2 == 0:
            success = True
            min_count = min(min_count, cnt2)
        # 남은 금액이 있다면, 추가 분할을 위해 큐에 추가
        else:
            frontier.append((v2, cnt2))

if success:
    print(min_count)
else:
    print(-1)