[백준] 9084 동전 python

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

9084번: 동전

동적 계획법은 볼때마다 새롭다. 요즘 계속 풀던 문제가 완전 탐색이었기 때문에 조금 더 오래 걸린 듯하다.

1, 5, 10 등 흔히 사용하는 동전만 나온다면 그리디 알고리즘으로 하는게 낫지만, 그렇지 않은 경우 동적 계획법을 사용해서 풀어야한다. 예를 들면 동전이 1, 4, 5이 있고 12원을 만들어야하는 경우 그리디 알고리즘으로 풀면 4개의 동전(5*2 + 1*2)이 필요하다. 하지만 4원 3개를 사용하면 12원을 만들수 있기 때문에 낮은 값이 아니므로 이 문제는 틀리게 된다.

대부분의 문제는 이렇게 최소로 만드는 문제를 찾는데 이 문제는 또 만들수 있는 방법의 개수를 찾아야해서 생각하기 조금 어려웠다.

우선, 동적계획법이므로 메모이제이션을 활용해야하는데 이때 저장하는 값은 특정 가격 m을 만드는 방법의 수라는 것은 쉽게 알수 있었다. 하지만 몇차원으로 만들어야하는지, 각 행과 열이 뜻하는 바가 무엇인지 생각하기 어려웠다. 

요즘 이차원 배열로 자주 접근하다보니 똑같이 이차원 배열에서 현재 고른 코인과 이전 state로 값을 갱신할까 생각했었다. 여기서 이전 state를 어떤 값으로 줘야할지 오래 고민하다가 결국 사용하지 않기로 했다.

두번째도 이차원 배열에서 벗어나지 못했다. 동전을 n개 고른 상태에서 m원을 만드는 방법의 개수를 저장하기로 했다. 배열은 (n+1)*(m+1)의 크기를 가지고 모든 값을 0으로 초기화했다. 오히려 이렇게 만드니 점화식을 세울수 있었다.

memo[i][j] = memo[i - 1][j] + memo[i][j - money[i]] (i, j >0)

memo[i][j] = memo[i - 1][j] + memo[i][j - money[i]] + 1 (j == money[i])

이렇게 점화식에 대한 코드로 제출했더니 통과가 되었다.

import sys; input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    money = list(map(int, input().split()))
    M = int(input())
    memo = [[0 for _ in range(M + 1)] for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, M + 1):
            tmp = 0
            tmp += memo[i - 1][j]
            if j == money[i - 1]:
                tmp += 1
            elif j - money[i - 1] > 0:
                tmp += memo[i][j - money[i - 1]]
            memo[i][j] = tmp

    print(memo[N][M])

 

하지만 이차원 배열이 아닌 일차원으로 충분히 할수 있을거라고 생각했다. 이것도 오래 걸렸는데 그냥 타인의 코드를 참고하기로 했다.

import sys; input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    money = list(map(int, input().split()))
    M = int(input())
    memo = [1] + [0 for _ in range(M)]

    for m in money:
        for i in range(M + 1 - m):
            memo[i + m] += memo[i]

    print(memo[M])

첫 열을 1로 만들고 값들을 누적시키는 방법으로 이차원을 일차원으로 압축할 수 있었다.

---

다 해보고 나니 그렇게 어려운 문제는 아니어서 더 허탈한 문제였다.

C++은 알고리즘도 똑같고 배열이나 vector만 사용하면되므로 굳이 하지 않을것이다.