[백준 - 2293] 동전 1 🟡

[백준 - 2293] 동전 1

❓ Problem

🤔 How

기본적인 DP 문제중 하나이다.
입력받은 target이 되도록하는 방법의 갯수를 구해야한다. dp테이블을 어떻게 접근해야할까 .

1. dp 테이블 접근하기

• 이 문제의 경우 각 액수에 맞게 가능한 방법으로 dp 테이블을 구성해주었다.
• dp[n] = n이 될수있는 조합의 방법수

2. 점화식

• dp[i]+=dp[i-coin] = i의 액수는 현재 사용할 코인이전의 방법가짓수에 이번 코인을 사용한것과 같다 즉 dp[i-coin] + coin 은 dp[i] 가 되므로 dp[i] 에는 현재 dp[i]에 dp[i-coin]를 더해줌으로서 방법을 추가한다.

❗ Solve

# 동전 1
import sys
input =sys.stdin.readline

def solution():
    n,k=map(int,input().split())
    coins=[]
    for _ in range(n):
        coins.append(int(input()))
    coins.sort()
    dp=[0]*(k+1)
    dp[0]=1
    for coin in coins:
        for i in range(coin,k+1):
            dp[i]+=dp[i-coin]
    print(dp[-1])

    pass
if __name__=="__main__": # 실행되는 부분
    solution()
    pass