[백준] 2293 : 동전1 / python

1. 문제 설명

2293번: 동전 1

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

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

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

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

 

입력

다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)

 

출력

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

 

2. 풀이 전 계획과 생각

• 10 -( -5, -2, -1) → 5, 8, 9
• ⇒ -5, -2, -1 연산이 3가지 경우이며, tree 구조로 내려간다.
• N -(-arr[0], -arr[1], ... arr[N-1] ) → n가지의 결과

재귀를 사용할 수 있지만, 계산이 중복된다.

→ arr에 계산한 값을 넣어, 중복 계산을 막자.

 

정의한 문제 : i값이 0에 도달하기 위한, 최소 연산 횟수

우리가 풀고자 하는 문제 : K값이 0에 도달하기 위한, 최소 연산 횟수

계산 저장할 자료구조 : 1차원 배열, index : 숫자, index값이 0의값에 도달하기 위한 최소 연산 횟수를 저장한다.

점화식 : ai = min(ai-coin_weight[0], ai-coin_weight[1], ai-coin_weight[N-1]) + 1

base : dp[0] = 0, dp[arr[0]] = 1, dp[arr[1]] = 1, ... dp[arr[N-1]] = 1

 

3. 1차 풀이 (문제 정의 잘못 함)

'''
우리가 풀고자 하는 문제 : N값이 0에 도달하기 위한, 최소 연산 횟수
계산 저장할 자료구조 : 1차원 배열, index : 숫자, index값이 0의값에 도달하기 위한 최소 연산 횟수를 저장한다.
점화식 : ai = min(ai-coin_weight[0], ai-coin_weight[1], ai-coin_weight[N-1])
base : dp[0] = 0, dp[arr[0]] = 1, dp[arr[1]] = 1, ... dp[arr[k-1]] = 1
'''

def coin1(weight_count, total_value):
    global coin_weight
    for w_idx in range(weight_count):
        dp[coin_weight[w_idx]] = 1

    for value in range(total_value+1):
        for w_idx in range(weight_count):
            if dp[value-coin_weight[w_idx]] < dp[value] and value > coin_weight[w_idx]:
                dp[value] = dp[value-coin_weight[w_idx]]
        dp[value] += 1

    print(dp[total_value])

weight_count, total_value = map(int, input().split())
coin_weight = []
for _ in range(weight_count):
    coin_weight.append(int(input()))
dp = [10000 for _ in range(total_value+1)]

coin1(weight_count, total_value)

 

4. 풀이하면서 막혔던 점과 고민

문제점

🤔  어디가 오류가 났을까?

 

점화식 : ai = min(ai-coin_weight[0], ai-coin_weight[1], ai-coin_weight[N-1]) + 1

• 접근을 잘못했다. 위의 점화식은, 해당 가치가 나오는 최소 연산을 구한 것이다.
• 문제에서 묻고자하는 것은 최소 연산이 아닌, 나올 수 있는 연산의 경우의 수를 묻는다.

⇒ 점화식을 다시 만들자.

 

새로운 점화식

n원를 만들 수 있는 경우의 수는

= 이전 가치들의 n원을 만들 수 있는 경우의 수

+ n원에서 현재 동전의 가치 k원를 뺀 가치의 경우의 수의 합

 

이것을 점화식으로 표현해보면,

f(n, k) = f(n-1, k) + f(n, k-W(n)) 이다.

 

dp 배열로 표현해보자.(i : 사용할 수 있는 weight의 범위) (k : 도달할 동전의 가치)

dp[i][k] = dp[i-1][k] + dp[i][k-w(i)]

 

5. 2차 풀이 (메모리 초과)

import sys

weight_num, goal_value = map(int, sys.stdin.readline().split())
weights = []
dp = [[0] * (weight_num + 1) for _ in range(goal_value+1)]

for _ in range(weight_num):
    weights.append(int(sys.stdin.readline().strip()))

# 중복 제거
weights = list(set(weights))

for w_num in range(1, weight_num + 1):
    for value in range(1, goal_value + 1):
       dp[w_num][value] = dp[w_num-1][value] + dp[w_num][value-weight]

print(dp[w_num][goal_value])

 

6. 풀이하면서 막혔던 점과 고민

🤔  2차원 배열을 1차원 배열로 만들어주어야 한다. 어떻게 하면 좋을까?

💡  Hint를 참고 했다.

      weight_num을 차원으로 두지말고, 반복문을 사용하자.

⇒   weight의 단계를 나타내는 차원을 없애야하는데,

weight의 단계가 있는 목적은, 특정 단계의 동전을 사용하는 것을 구현하기 위함이다.

그러면, 굳이 weight의 단계의 차원을 둘 것이 아니라,

특정 단계를 사용하는 동전을 반복문으로 사용하고,

다음 동전의 단계로 넘어가서 또 반복문을 취하면 되기에 차원을 축소 할 수 있다.

 

dp[value] = dp[value] (기존 동전의 weight들을 이용해 value를 만드는 경우)

                    + dp[value-weight] (새로운 동전의 weight를 사용하는 경우 추가)

 

7. 3차 풀이

import sys

weight_num, goal_value = map(int, sys.stdin.readline().split())
weights = []
dp = [0 for _ in range(goal_value+1)]
dp[0] = 1

for _ in range(weight_num):
    weights.append(int(sys.stdin.readline().strip()))

# 중복 제거
weights = list(set(weights))

for weight in weights:
    for value in range(1, goal_value+1):
        if value - weight >= 0:
            dp[value] += dp[value-weight]

print(dp[goal_value])

 

8. 풀이 후 알게된 개념과 소감

• 풀고자하는 문제의 정의를 잘해주자.
• 문제를 해결하기 위한 규칙을 잘 찾아보자.