[Python] 백준 온라인 저지 2293번

실버 1  https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

 

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다.

이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오.

각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

 

 

[Python]

 

풀이 방법:

 

동적 계획법(Dynamic Programming, DP) 문제

• '전체의 문제'를 '부분 문제'로 잘 나누었는가? 그렇다면 전체 문제를 해결하기 위한 부분 문제의 점화식은 무엇인가?
• 부분 문제들을 해결하며 얻는 결과 값을 메모제이션 하는지
• 부분 문제의 점화식은 부분 문제들 사이의 관계를 빠짐없이 고려하는지

 

• 전체의 문제: 가치의 합이 k원이 되는 경우의 수
• 부분 문제:
  • 가치의 합이 i (1 <= i <= k)원이 되는 경우의 수
  • 특정 동전을 썼을 때 가치의 합이 i원이 되는 경우의 수
• 입출력 예시로 다른 예시를 생각해보며 테스팅 해볼 것
• 각각의 숫자를 (1, 2, 5) 더해 숫자를 나타내는 방법을 나타낸 표
• dp[ j ]에 dp[ j  -  i ]의 총 개수를 쭉 더해주면 된다

 

	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
i = 1	개수(1)	1 개수(1)	1 + 1 개수(1)	1 + 1 + 1 개수(1)	1 + 1 + 1 + 1 개수(1)	1 + 1 + 1 + 1 + 1 개수(1)	1 + 1 + 1 + 1 + 1 + 1 개수(1)
i = 2			2 개수(1)	1 + 2 개수(1)	1 + 1 + 2 2 + 2 개수(2)	1 + 1 + 1 + 2 1 + 2 + 2 개수(2)	1 + 1 + 1 + 1 + 2 1 + 1 + 2 + 2 2 + 2 + 2 개수(3)
i = 5						5 개수(1)	5 + 1 개수(1)

 

 

코드:

import time
import sys
sys.stdin = open("input.txt", "r")
# input = sys.stdin.readline
start_time = time.time()

# source code

n, k = map(int, input().split())
c = [int(input()) for i in range(n)] # 코인의 종류
dp = [0 for i in range(k+1)] # 사이즈 k+1만큼의 리스트 선언
dp[0] = 1 # 인덱스0은 동전을 1개만 쓸 때의 경우의 수를 고려하기 위해 선언

for i in c:
    for j in range(1, k + 1):
        if j - i >= 0:
            dp[j] += dp[j - i]

print(dp[k])

#

end_time = time.time()
print("WorkingTime: {} sec".format(end_time-start_time))

 

 

 

 

추가 예정 - [Javascript]

풀이 방법:

정답: