문제 링크
https://www.acmicpc.net/problem/9084
https://www.acmicpc.net/problem/2293
🛠️ 미해결
- 풀이시간 : 1시간 30분
- 틀린 이유
- dp를 사용해서 푼 다는 점을 생각하고 접근하였다. dp를 사용하기 위해 금액을 기준으로 dp를 넣는다는 것도 파악했고, dp에 키가 금액이 온다는 것도 파악했다. 점화식 또한 전의 금액의 dp의 합, 즉 방법들의 합이 현재의 dp라는 점도 생각하였다. 하지만 계속해서 방법이 중복되서 계산되는 문제가 발생하였다.
- 그렇기 때문에 금액부터 따질 경우, 문제가 발생한다는 것을 알게되었다. 하지만 방법을 만질 방법이 더 생각나지 않았다. 그 이유는 몇 가지 있다. 금액이 기준이고 그 다음 동전이 온다고 생각했기 때문에 for문의 순서가 반드시 금액으로 dp를 갱신하면서 이에 따라 동전을 따져야 한다고 생각했다. 하지만 꼭 기준점이 먼저 for문으로 올 필요가 없었다. 이러한 문제는 처음 접하기도 하고 이러한 방법도 처음 접하였다. 보통은 기준이 바깥 for문으로 온다는 편견이 있었던거 같다.
- 그리고 방법을 생각해내지 못한것이 두 번째 틀린 이유였다. 그 말은 즉슨, 작은 동전부터 골라서 dp를 갱신하는 것이 왜 중복을 피하는 방법이 되는지를 몰랐던 것이다. 방법의 합을 생각하지 못한 것이다. 동전 하나만 사용했다면 dp가 금액에 따라 갱신되는 것과 같은 문제였으며 숫자가 올라가는 것과 같은 문제였다. 즉 작은 금액으으로 이룰 수 있는 수를 전부 만든 다음에 그 수에 다른 동전 하나로 되는 모든 방법을 구하는 것이다. 즉 다른 종류의 dp를 합쳐놨다고 할 수 있다. 이 것을 생각해내지 못하였다.
- 왜 생각해내지 못하였는가? 동전 단위로 dp를 따져볼 생각을 하지 못하였다. 하나의 동전이 아닌 전체 동전 단위로 생각하였다. 한꺼번에 진행을 하니 순서가 생긴다는 것을 인지하지 못한 것이다. 즉 어떤 것을 동시에 진행할 경우, 즉 하나의 순간에 쌓이는 방법을 반복적으로 선택한다면 순서가 생긴다는 것이다. 순서를 없애주기 위해서는 별개로 진행해야 한다는 것을 깨달았다.
- 왜 순서를 없애주기 위해 별개로 진행해야 된다는 사실을 알아차리지 못했을까? 분리해서 생각하려고 하지 않았을까? 왜 같이 가야하는 요소로 생각했을까? 아마 현재의 해를 구하기 위해서 전의 해로 완성시켜야 한다는 것에 몰두되여 현재의 해가 한번에 나와야 한다고 생각했기 때문인거 같다. 현재의 해는 한번에 갱신되야 한다고 생각한 것이다. dp라고 해서 한번에 답이 나오는 것이 아닌 여러 dp의 누적이나 합으로 이루어질 수 있다는 생각을 넓혀야 겠다.
🕒 Python 풀이시간: x
# 동전으로 목표 금액을 만드는 경우의 수를 구하는 함수
def solve():
n = int(input()) # 동전 종류의 수
coinsType = list(map(int, input().split())) # 동전 종류
m = int(input()) # 목표 금액
# dp 배열 초기화: dp[i]는 금액 i를 만들 수 있는 경우의 수를 저장
dp = [0] * (m + 1)
dp[0] = 1 # 금액 0을 만들 수 있는 경우의 수는 1 (동전 하나도 사용하지 않는 경우)
# 각 동전을 사용하여 dp 배열 갱신
for coin in coinsType:
for i in range(coin, m + 1):
dp[i] += dp[i - coin]
# dp[m]에 목표 금액을 만들 수 있는 경우의 수가 저장됨
print(dp[m])
# 여러 테스트 케이스 처리
for _ in range(int(input())):
solve()동전 문제: 주어진 금액을 만드는 방법 세기! 💰🔢
동전으로 주어진 금액을 만들 수 있는 방법을 세는 문제이다. 단순히 갯수에 따라 방법의 종류를 나누기 때문에 한 방법의 동전을 나열했을 때, 순서가 없다.
그렇기에 각 금액에 따라 현재의 금액을 구할 수 있다는 것을 알 수 있다. 현재의 dp[i]에는 dp[i-coin]을 더해온 값이 되는 것이다. 하지만 이 때, 문제가 있다. 현재의 금액을 기준으로 모든 동전의 종류를 따지면 전의 동전의 방법 뒤에 그 종류가 오는 것이기 때문에 순서가 생겨버린다. 우리는 순서가 필요하지 않다.
순서가 생기지 않기 위해서는 동전의 종류부터 따져야 한다. 즉, 1원으로 만드는 모든 방법을 구하는 것이다. 그 다음 2원으로 만드는 모든 방법을 그 방법위에 더하는 것이다. 그러면 오로지 동전의 각 종류에 따라서 방법의 결과가 누적되는 것이다. 순서가 없어지고 동전의 갯수의 증가폭에 따라 따져지는 것이다. 그렇기 때문에 작은 순으로 동전을 나열된 순으로 가져와 dp를 동전의 금액에 따라(금액의 증가폭) 갱신시켜주면 답이 나온다.
이렇게 Python으로 백준의 "동전" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
