백준 2293 동전 1

동전 1

문제는 백준에서 확인 할 수 있다.

✔ 접근방법

• DP

1. (k+1)개의 인덱스를 가진 dp 배열 생성
2. dp[i]는 숫자 i를 만들기위한 경우의 수
3. 점화식
   3-1. dp[i] = dp[i] + dp[i-(사용하고자하는 동전)]

입력받은 동전을 순회하면서 dp배열을 생성하면, 답을 얻을 수 있다.

✔ 코드

import sys

def solution(arr, k):
    
    dp = [ 0 for _ in range(k+1) ]
    
    '''
        dp[idx]는
        arr의 i번째 인덱스까지 루프를 돌았을 때
        idx를 만족하는 조합의 수
    '''

    for i in arr:
        for idx in range(len(dp)):
            if idx - i == 0:
                dp[idx] += 1
            elif idx - i < 0:
                continue
            else:
                dp[idx] = dp[idx]+dp[idx-i]
        # print(dp)

    return dp


if __name__ == "__main__":
    n, k = map(int, input().split())

    arr = []
    for _ in range(n):
        arr.append(int(sys.stdin.readline().rstrip()))

    arr.sort()
    ret = solution(arr, k)

    print(ret[-1])

☝ 팁

처음에는 DFS 백트래킹을 해야하나 생각하고 접근하였다.
하지만, dp문제 였고 점화식 세우기가 어려웠다.

아래는 점화식 이해에 참고했던 포스팅
https://velog.io/@juno7803/BOJ-2293-%EB%8F%99%EC%A0%84-1