백준 2293번

참고 : https://seongonion.tistory.com/108

 

 

# import numpy as np
# import collections as co

def getWays(n, c):
    # rc = [i for i in c if i <= n]
    """
    DP 문제는 결과값에 대한 분할로 생각하면 된다.
    DP문제에서는 주로 list를 사용하며, list의 마지막 값이 최종 결과값으로 산출된다.
    따라서 index가 순서로 여기고, list[index]가 index에 대한 결과값으로 생각하고 풀어보자.
    
    0<i<n일때, dp[i]는 i라는 수에 대한 경우의 수(정답)
    dp[n]이 최종 정답
    """
    dp = [0 for i in range(n+1)]        #
    dp[0] = 1               # dp[0]은 동전 1개만 사용했을 때
    print(dp)

    for coin in c:
        for i in range(coin, n+1):
            tmp = dp[i - coin]
            dp[i] += tmp
            print(dp)

    return dp


if __name__ == '__main__':
    # n = int(first_multiple_input[0])
    # m = int(first_multiple_input[1])
    # c = list(map(int, input().rstrip().split()))

    n = 4
    c = [1,2,3]

    ways = getWays(n, c)

    print(ways)