[백준알고리즘] 11047번: 동전 0 -Python

[백준알고리즘] 11047번: 동전 0 -Python

https://www.acmicpc.net/problem/11047

11047번: 동전 0

그리디 알고리즘(탐욕 알고리즘)의 문제이다. 그리디 알고리즘의 경우에는 동적 계획법과 달리 항상 최적의 해를 준다고 보장되지 않는다. 각 Step에서 Decision에 의해서는 Optimization Value를 선택하지만, 전체를 봤을 때에는 Optimization이 보장되지는 않는다는 말이다. "Sequence of Choice"라고봐도 될 것이다.

 

그리디 알고리즘이 사용되는 대표적인 예로는 Minimum spanning tree(최소 신장 트리)를 구성하는 데에 사용되는 알고리즘 중 하나인 "프림 알고리즘" (최소 신장 트리 구성에 사용되는 알고리즘의 대표적인 다른 예는 크루스칼(Kruskal) 알고리즘이 있다)이다. "프림 알고리즘"을 간략히 설명하면, Weighted Graph에서 Tree를 구성하기 위한 알고리즘 중의 하나이며, 그래프의 임의의 한 Vertex에서부터 시작하며 Vertex를 추가해가며 Sub tree를 확장해나간다. 이때 Vertex를 추가하는 아이디어로, Sub tree에서 추가할 수 있는 Vertex(Sub tree에 추가가 되지 않았으며 Sub tree와 Edge가 직접 연결되어 있는 Vertex)들 중에서 Sub tree와의 Edge의 Weight가 가장 작은 Vertex를 추가하는 방법이다.

여기서 Vertex를 추가할때마다 추가할 수 있는 Edge들 중에서 가장 Optimal인 선택을 하기 때문에 Greedy Algoritm이다. 그렇기 때문에 프림 알고리즘의 결과 역시 반례가 존재할 수 있는 알고리즘이며 항상 Optimal인 Minimum spanning tree를 제공하지는 않는다.

 

하지만 코드를 작성하는 데에 있어서는 각 Step에서 Optimal을 고르는 그리디 알고리즘의 특성덕에 동적 계획법보다도 쉽게 작성할 수 있다.

종료 조건, 선택 조건만 잘 맞게 구현하며 반복시키면 된다.

 

여기서는 종료 조건이란 동전의 가치의 합들이 주어진 가치와 같으면 종료이며, 가치가 큰 동전부터 시작하며 매 단계마다 필요한 가치를 고려하면서 필요한 가치를 현재의 동전으로 보탤 수 있으면 보탤 수 있는 만큼 동전을 챙기면 됩니다.

해석이 조큼 복잡한 것 같지만.. 문제를 파악하기에는 쉽기 때문에 그냥..

 

코드로 들어가기 전에, 문제에는 다음과 같은 조건이 있기 때문에 항상 주어진 K를 만족시킬 수 있습니다만 주어진 동전들로 K를 구성하지 못하는 경우도 포함시켜서 구현해봤습니다.

A1 = 1 이기 때문에 항상 주어진 K를 만족시킬 수 있음

 

처음에는 Stack을 이용해서 구현해봤다.

이 설명은 문제를 해결하기 위해서 상관이 없는 부분이다. pop()이 있는 부분이 주어진 동전으로 K를 만족시킬 수 없는 부분이다. 주어진 동전으로 만족시킬 수 없으면, 마지막에 추가된 동전들을 전부 제외시키고 그전에 추가했던 동전도 한 개 뺀다. 예를 들어 2 7 13 17로 56을 만족시키기 위해서는 스택 구성이 다음과 같아진다. ( (괄호) 안의 값은 56 - stack안의 값)

 

stack: 17 (39)

stack: 17 17 (22)

stack: 17 17 17 (5)

stack: 17 17 17 2 (3)

stack: 17 17 17 2 2 (1)

stack: 17 17 (22)

stack: 17 17 13 (9)

stack: 17 17 13 7 (2)

stack: 17 17 13 7 2 (0)

 

보다시피 더이상 K를 구할 수 없다면 (22)까지는 가야지 다른 시도를 할 수 있기 때문에 저때까지 pop()을 해줍니다.

 

구현했던 코드는 다음과 같다.

import sys

N, K = map(int, sys.stdin.readline().split())
coin = []
for i in range(N):
    coin.append(int(sys.stdin.readline()))

stack = []
idx = N - 1
target = K
while target < coin[idx]:
    idx -= 1
stack.append(coin[idx])
target -= coin[idx]

while stack:
    if target == 0:
        break
    
    if idx < 0:
        t = stack.pop()
        target += t
        while t == stack.pop():
            target += t
        target += t
        idx = coin.index(t) - 1
        continue
    
    if target < coin[idx]:
        idx -= 1
        continue

    stack.append(coin[idx])
    target -= coin[idx]

print(len(stack))

 

하지만 stack으로 구현했을 때에는 시간 초과가 발생했다. 어느 정도 예상은 했었던 결과이다. 그래서 바로 N의 크기의 리스트를 만들고 다음과 같이 구현했다.

여기서도 K를 만족시킬 수 없으면 수행되는 코드가 있다. 볼때 감안하고 보면 if idx < 0: 부분만 제외하고 보면 된다.

 

import sys

N, K = map(int, sys.stdin.readline().split())
coin = []
for i in range(N):
    coin.append(int(sys.stdin.readline()))

target = K
need = [0 for _ in range(N)]
idx = N - 1
last_idx = N - 1
lastlast_idx = N - 1
while target != 0:
    if idx < 0:
        target += coin[last_idx] * need[last_idx]
        need[last_idx] = 0
        target += coin[lastlast_idx]
        need[lastlast_idx] -= 1
        idx = lastlast_idx - 1
        continue
        
    if target < coin[idx]:
        idx -= 1
        continue
    
    need[idx] = target // coin[idx]
    target %= coin[idx]
    lastlast_idx = last_idx
    last_idx = idx


print(sum(need))

 

2020.03.06

새로 문제를 풀어봤다. 코드가 더 간결하게 나와서 올리기로 했다.

 

그리고 문제를 풀면서 본 조건인데,  "i ≥ 2인 경우에 Ai는 Ai-1의 배수" 이 부분이다. 이 부분 덕분에 이 문제는 그리디 알고리즘으로 해결이 가능한 것이다. 이 조건이 없었다면 다음과 같은 입력에 대해서는 그리디 방식으로 처리가 불가능하다.

4 14

1

4

5

6

 

최소 코인의 갯수는 5원 2개, 4원 1개로 3개이지만, 그리디 방식으로 한다면 총 4개가 나올 것이다. 하지만 해당 조건 덕분에 항상 큰 수에서 먼저 최대한 고르는 것이 유리하게 되는 것이다.

import sys

n, k = map(int, sys.stdin.readline().split())
coin = [int(sys.stdin.readline()) for _ in range(n)]

cnt, total = 0, 0
for i in range(len(coin) - 1, -1, -1):
    if total == k:
        break
    remain = k - total
    if remain > coin[i]:
        cnt += (remain // coin[i])
        total += (coin[i] * (remain // coin[i]))

sys.stdout.write(str(cnt))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다