on1ystar 머릿속을 정리, 기록하는 곳

<백준 2293번-python> 동전 1

21 Feb 2021


풀이 시간 : 한 번에 못품

시간 제한 : 0.5 초 (추가 시간 없음)

메모리 제한 : 4 MB

출처 : 백준-2293번 https://www.acmicpc.net/problem/2293


문제

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

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


입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.


출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.


내가 적어본 문제 풀이

처음에 접근했던 방법은 dp 배열은 만들고, 1부터 k까지 순회하면서 만들어야 하는 값에서 각 동전의 가치를 뺀 다음 그 값을 인덱스로 하는 dp 배열의 값을 더해주는 방법이다.

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

하지만 이 방법을 사용하면 중복의 경우까지 더해버린다. 예를 들어 입력값이 아래와 같을 때,

3 10
1
2
5

dp 배열을 출력해 보면 값이 너무 커진다.

i=1:  [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2:  [1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0]
i=3:  [1, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0]
i=4:  [1, 1, 2, 3, 5, 0, 0, 0, 0, 0, 0]
i=5:  [1, 1, 2, 3, 5, 9, 0, 0, 0, 0, 0]
i=6:  [1, 1, 2, 3, 5, 9, 15, 0, 0, 0, 0]
i=7:  [1, 1, 2, 3, 5, 9, 15, 26, 0, 0, 0]
i=8:  [1, 1, 2, 3, 5, 9, 15, 26, 44, 0, 0]
i=9:  [1, 1, 2, 3, 5, 9, 15, 26, 44, 75, 0]
i=10:  [1, 1, 2, 3, 5, 9, 15, 26, 44, 75, 128]

왜냐하면 i=3일 때를 보면 알 수 있는데, 3을 만들 수 있는 경우의 수는 총 2가지다.

  • 1을 3개 사용
  • 1을 1개 사용, 2를 1개 용

하지만 위 알고리즘은 경우의 수를 3으로 계산해버린다.

  • dp[3] += dp[3-1] → 1을 1개 쓰고, 나머지 2를 만드는 경우의 수
    1. 1을 2개 사용
    2. 2를 1개 사용 (중복)
  • dp[3] += dp[3-2] → 2를 1개 쓰고, 나머지 1을 만드는 경우의 수
    1. 1을 1개 사용 (중복)

따라서 위 알고리즘에서 중복을 없애는 방법을 고민하는 것보다 접근을 다르게 해야 한다.

기준을 조금 바꿔 큰 틀을 k에 맞추는 것이 아니라 coin을 사용하는 갯수에 맞추는 것이다. 예를 들어 k를 1로만 만들 수 있는 경우의 수들을 먼저 dp에 저장한다. 그 다음 2를 추가해서 만들 수 있는 경우의 수를 원래 dp에 더해 나간다.

coin=1: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
coin=2: [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
coin=5: [1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10]

coin=5일 때 i=5부터 보면,

  • i=5일 때, 5를 1개 쓰면 남은 값 = 0 → 따라서 기존에 1과 2만을 사용해서 만들 수 있는 경우의 수인 dp[i]에 5를 1개 쓰는 경우 dp[0] = 1만 추가

위와 같이 coin과 i가 동일한 경우들 때문에 dp[0] = 1로 초기화를 해야 한다.

  • i=6일 때, 5를 1개 쓰면 남은 값 = 1 → dp[i](기존) + dp[1](1을 만들 수 있는 경우의 수)
  • …
  • i=10일 때, 5를 1개 쓰면 남은 값 = 5 → dp[i](기존) + dp[5](5를 만들 수 있는 경우의 수)

자연스럽게 5를 2번 사용하는 경우의 수도 추가

코드도 결과적으로 간단하게 for문의 안과 밖을 바꿔주면 된다.

for coin in coins:
    for i in range(1, K+1):
        if i//coin == 0:
            continue
        dp[i] += dp[i - coin]


전체 코드 - github.com/on1ystar/algorithm-problem-solving-codes

Related posts