[백준 2293 파이썬]동전 1 풀이

문제

n가지 종류의 동전이 있고 각 동전은 서로 다른 가치를 나타낸다

그 동전을 합이 k 가 되도록 하는 경우의 수를 구한다 단 가각의 동전은 몇개라도 사용할 수 있다

사용한 동전의 구성이 같은데 수선만 다른 경우는 같은 경우이다

 

입력

첫줄에 n,k 가 주어지고 다음 n개의 줄에 각 동전의 가치가 주어진다

 

출력

경우의 수를 출력한다 

 

코드

-처음 생각할때 완전 탐색 방식을 생각하여 문제를 풀었다 

def msum(count,result):
    global ans
    if result >k:
        return
    elif result==k:
        ans+=1
    else:
        msum(count,result+data[count])

        if count<len(data)-1:
            msum(count+1,result)

그러나 시간 초과가 생겨 조건을 확인하니 시간 제한이 0.5초 인걸 확인 할수 있었다 

 

다른 방식으로 dp를 이용한 풀이을 생각하였다

dp=[0]*(k+1)
dp[0]=1
for i in data:
    for j in range(i,k+1):
        dp[j]+=dp[j-i]

 

풀이로 예로 들면 우리가 원하는 k가 3 이고 주어진 동전의 가치가 1,2, 일때

1이될 경우수는 1

2가 될 경우수는 2=>  1+1, 2

3이 될 경우수는  2=> 1+1+1, 2+1

 

dp[i-코인의 값]의미는  그 코인으로 i 값이 되기 위한 경우수를 나타낸다 그렇기에 이러한 방식을 사용하면  중복의 경우의수를 제거할수 있다.

 

코드

n,k=map(int,input().split())
data=[]
ans=0
for i in range(n):
    a=int(input())
    data.append(a)


dp=[0]*(k+1)
dp[0]=1
for i in data:
    for j in range(i,k+1):
        dp[j]+=dp[j-i]
print(dp[k])

dp[0]=1을 하는 이유는 각 코인에 기본 값을 주기 위해서 이다 

1의 가치를 가진 코인으로 1을 만든데 필요한 경우수는 1이고

2의 가치를 가진 코인으로 2를 만든데 필요한 경우수는 1이기에 기본으로 각 코인에 대한 경우수를 주기 위해