2293. [Python]동전 1

1. 문제

 

 

2. 접근 방법

 

• 시간 제한: 0.5초
• 메모리 제한: 4MB
• DP

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline

n, k = map(int,input().split())
# 동전 저장 리스트
coins = []

# 동전 저장
for _ in range(n):
    coins.append(int(input()))
# 동전 정렬
coins.sort()

dp = [0] * (k+1)
# 0원을 만드는 방법도 1개
dp[0] = 1
# 동전 반복 진행
for coin in coins:
    # 초기값 동전부터 1씩 더해나감
    for i in range(coin,k+1):
        # i번째 동전의 경우 i-coin 한 값을 더해나가야함 동전이 계속 값이 바뀌기 때문에
        dp[i] += dp[i-coin]

print(dp[-1])

 

4. 문제를 풀고난 후 생각

 

• 내가 생각하기엔 DP의 기본적인 문제였고, 실제 동전을 인풋을 받은 후 초기 dp 값을 k+1 까지 설정해준 후 dp[0] 을 1로 초기 세팅을 진행했다.
• 0 원을 만드는 방법은 0원을 넣는 것이기 때문에 초기 값을 1로 설정해줬다.
• 동전이 들어오는 크기가 순서가 없기 때문에 작은 동전부터 오름차순으로 sort 처리를 해줬다.
• 이후 동전 한개씩 반복문을 진행하며 동전 인덱스 - 현재 동전 을 빼준 dp 값을 계속해서 갱신해줬다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• DP(다이나믹 프로그래밍)