[백준] 2293번 : 동전 1 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

https://www.acmicpc.net/problem/2293

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 동전을 여러 개 사용하여 가치의 합을 맞출 수 있는 모든 경우의 수를 구하는 문제이다.

모든 경우의 수를 다 찾을 수 없으므로 동전의 가치가 가장 작은 것부터 가치의 합을 1부터 k까지 각 경우의 수를 차례대로 구하여 저장한 다음, 가치가 큰 동전을 하나씩 불러오며 해당 동전만으로 만들 수 있는 값을 구해 그 경우의 수를 이전 경우의 수에 추가한다.

예제를 예시로 보면 동전의 가치가 가장 작은 1부터 각 가치를 1만 사용하여 경우를 구한다.

다음으로 2만 사용하여 경우를 이전의 경우에 추가하여 구한다.

여기서 2는 0의 경우에 2를 추가한 경우이고, 3은 1의 경우에 2를 추가한 경우이다.

4는 2의 경우에 2를 추가한 경우이고, 5는 3에 2를 추가한 경우이다.

이렇게 계속 동전의 가치를 올리며 각 동전으로만 만들 수 있는 경우를 이전 경우에 추가한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 동전의 개수와 가치의 합을 입력받는다. n, k = map(int, sys.stdin.readline().split())
3. 각 동전의 가치를 저장할 리스트를 생성한다. coin = list()
4. 동전의 개수만큼 반복하며 동전의 가치를 입력받아 리스트에 추가한다. for _ in range(n): coin.append(int(sys.stdin.readline()))
5. 각 값마다 경우의 수를 저장할 배열을 생성하고 초기화한다. dp = [0] * (k + 1)
6. 값이 0이 되는 경우는 없지만 동전의 가치 해당 값 1개로만 사용하여 값을 만들 수 있으므로 해당 경우를 추가하기 위해 0이 되는 경우를 1로 저장한다. dp[0] = 1
7. 동전의 가치가 가장 작은 동전부터 하나씩 가져오고 해당 동전으로만 만들 수 있는 경우의 수를 구하여 경우의 수에 추가한다. 경우의 수를 구할 때는 동전 가치의 값부터 경우의 수를 세어주면 되고 또한 값에서 동전의 가치를 빼준 경우의 수에 해당 경우의 수를 더해주면 된다. for c in coin: for num in range(c, k + 1): dp[num] += dp[num - c]
8. 최종적으로 모든 동전에 따른 경우의 수를 모두 추가하여 경우의 수를 구한 뒤, 최종 맞추려는 값의 경우의 수를 출력한다. print(dp[k])

728x90

3. 소스코드

import sys

n, k = map(int, sys.stdin.readline().split())
coin = list()
for _ in range(n):
    coin.append(int(sys.stdin.readline()))

dp = [0] * (k + 1)
dp[0] = 1
for c in coin:
    for num in range(c, k + 1):
        dp[num] += dp[num - c]

print(dp[k])