[백준] 2293. 동전 1 (python)

• 문제 출처:
  동전 1

0. 서론

동적 계획법 (Dynamic Programming)을 이용하여 푸는 문제이다.
다만, 메모리 제한이 4MB인 만큼, 메모리 관리에 주의하여 풀 필요가 있다.

1. 풀이 방법

문제를 풀 때 가장 어려웠던 부분은 "사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다."라는 조건을 처리하는 부분이었다.

우선 해당 조건을 고려하지 않고, 문제를 풀어보도록 하자. 입력값은 테스트 케이스 (1원, 2원, 5원으로 10원 만들기)와 같다고 가정한다.

(목표값, 사용 동전)

- 0원 : 0개

- 1원 : 1원 1개

- 2원 : 1원 2개 / 2원 1개

- 3원 : 1원 3개 / 2원 1개, 1원 1개

- 4원 : 1원 4개 / 2원 1개, 1원 2개 / 2원 2개

- 5원 : 1원 5개 / 2원 1개, 1원 3개 / 2원 2개, 1원 1개 / 5원 1개

...

가령 5원을 만든다고 했을 때에는, "4원을 만드는 경우의수 + 1, 3원을 만드는 경우의 수 +1, 0원을 만드는 경우의 수 +1"라고 생각할 수 있겠지만, 이런 경우는 "사용하는 동전의 종류는 같지만, 순서가 다른 경우"를 고려할 수 없다는 단점이 있다.

따라서 동전을 선택하는 for문, 목표 금액을 정하는 for문으로 2중 for문을 구성하여, 한 번 동전을 선택하여 for문을 돌고 난 후에는 해당 동전을 더 이상 고려하지 않는 방법으로 문제를 해결하고자 한다.

우선 1원 짜리만을 사용하여 목표 금액을 만드는 방법이다.

1원 동전으로는 1원을 만들 수 있기 때문에, dp[1] = 1으로 초기화를 해준다.

2원은 1원 동전 2개로, 3원은 1원 동전 3개로 만들 수 있으며, 마찬가지로 10원은 동전 10개로 만들 수 있다.

dp[i] += dp[i - coin]

이를 위와 같은 식으로 나타낼 수 있으며, 위 사진과 같이 배열을 갱신할 수 있다.

다음은 2원 짜리를 고려하여 목표금액을 만드는 방식이다.

2원 하나로는 2원을 만들 수 있기 때문에 dp[2] += 1을 해준다. 여기서 dp[2]가 나타내는 것은 1원 짜리와 2원 짜리로 2원을 만들 수 있는 경우의 수이다.

그리고 위 점화식을 통해 다른 값들도 갱신해준다.

dp[3]은 dp[3] + dp[1]로 갱신되었는데, 여기서 앞의 dp[3]은 3을 1원 짜리로만 만든 경우의 수 (111)이며, 뒤의 dp[1]은 1원짜리로 1을 만든 경우의 수 (1)인데, dp[1]을 왜 더하냐면, 1원에 2원 동전을 사용하면 3원이 되기 때문이다.

따라서, 갱신 후의 dp[3]이 가지는 '2'라는 값은 두 가지 경우의 수 (111, 12)를 의미한다.

dp[4]는 dp[4] + dp[2]로 갱신되었는데, 여기서 앞의 dp[4]는 4를 1원짜리 동전으로 만든 경우의 수 (1111)이며, dp[2]는 앞에서 이미 갱신을 해 주었으므로 1원짜리와 2원짜리로 2를 만드는 경우의 수 (11, 2)이다. dp[2]에 2원 짜리 동전을 더하면 4원이 되기 때문에, 갱신 후의 dp[4]가 가지는 '3'이라는 값은 (1111, 112, 22)를 의미한다.

위와 같은 과정을 모든 동전에 대해 반복하면 최종적으로 목표하는 값을 찾을 수 있다.

2. 코드

import sys
input = sys.stdin.readline

# 입력 받기

num_coins, obj = map(int, input().split()) # 동전의 종류, 목표 금액
coins = [int(input()) for _ in range(num_coins)] # 동전의 종류를 저장할 배열

# 목표 금액보다 큰 동전 제거 (목표 금액은 10,000원 이하이지만, 동전의 가치는 100,000 이하이기 때문)
coins = [coin for coin in coins if coin <= obj]
num_coins = len(coins)

# DP 배열 초기화
dp = [0] * (obj+1) # dp[i] : i원을 만들 수 있는 경우의 수

# DP 배열 갱신
for coin in coins: # 동전을 하나 선택
    dp[coin] += 1 # 해당 동전을 처음으로 사용하는 경우 

    for col_idx in range(len(dp)): # dp 배열 내의 모든 원소 탐색
        if col_idx - coin >= 0: # 범위 확인
            dp[col_idx] += dp[col_idx - coin]


# 정답 출력
print(dp[obj])