동전1

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

2293번: 동전 1

문제 요약:

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

 

난이도:

골드5

 

소요시간:

45분

 

제출횟수:

2회

 

1차 코딩:

import sys
input = sys.stdin.readline

n,k = map(int,input().split())

arr = [int(input()) for _ in range(n)]
dp = [[0]*n for _ in range(1+k)]

for i,p in enumerate(arr):
    dp[p][i] = 1

for x in range(n):
    for y in range(k+1):
        if arr[x]<=y:
            dp[y][x]= dp[y-arr[x]][x] + dp[y][x-1] + dp[y][x]
        else:
            dp[y][x]=dp[y][x-1]

print(dp[-1][-1])

일단 메모리가 오버된 2차원 배열 로 짠 DP입니다. x값은 코인의 종류 개수를 y값은 나타낼 돈을 의미합니다.예를 들어보면 8을 나타내려 했을때, 1과 2로만 만들려고 하면 11111111,1111112,111122,11222,2222 이렇게 5개를 만들 수 있습니다. 하지만 5를 추가 하게 되면 위의 5개를 포함해서 1115, 125를 즉 두개를 더 추가 할 수 있습니다. 이때 5를 제외하면 111, 12 인데 이는 8에서 5를 뺀 3을 1,2,5를 사용해서 만든 값들 입니다. 즉 현재 만들어야 할 값( y ) 에서 사용하고 있는 동전( arr[x] ) 을 뺀 값을 만드는 경우가 dp[y-arr[x]][x] 이고 지금 사용하고 있는 동전을 사용하지 않고 이전 동전까지(x-1)만 사용해서 지금 값(y)을 만드는 경우의 수가 dp[y][x-1]입니다. 그리고 이때 새로운 동전을 추가 시키기 위해 새로운 동전과 나타래려는 값이 같을 때 (즉 5를 나타래려고 할때 코인이 5라면 이전에서 한개 추가) 를 위해 미리 dp위치에 1을 할당해놓고dp[y][x]를 더해주었습니다. 이는 아래 개선된식에서 더깔끔하게 나타내겠습니다. 그리고 아직 사용동전이 너무커서 값을 나타낼수 없을때는 이전동전의 경우의 수와 같습니다.

 

2차코딩:

import sys
input = sys.stdin.readline

n,k = map(int,input().split())

arr = [int(input()) for _ in range(n)]
dp = [0]*(1+k)

for x in range(n):
    for y in range(k+1):
        if arr[x]<=y:
            dp[y]= dp[y-arr[x]] + dp[y] + (y==arr[x])
print(dp[-1])

메모리가 할당된것 보다 초과가 됐기 때문에 2차원 배열을 1차로 줄여보았습니다. 아까와 똑같은 로직이지만, 동전이 클때 아무것도 할당을 안함으로써 이전의 값이 유지가 되고, 동전값과 나타낼값이 같을때 y==arr[x]로 (맞다면 1 아니라면 0) 깔끔하게 나타내주었습니다.