동전 교환에서 루프 순서가 조합과 순열을 가른다

1, 5, 10, 50, 100, 500원으로 특정 금액을 만드는 방법이 몇 가지인지 세는 문제다.

재귀로 세기

def rec(cur=0):
    if cur == n:
        global sum
        sum += 1
        return
    if cur > n:
        return

    for i in [1, 5, 10, 50, 100, 500]:
        rec(cur + i)

n = 6
sum = 0
rec()

금액을 하나씩 더해가다 정확히 맞으면 하나로 센다. n = 6 이면 3이 나온다.

3이 맞는지 세어보면 1+1+1+1+1+1, 1+5, 5+1 세 가지다. 1+5 와 5+1 이 따로 세어진다.

동전을 내는 순서가 다르면 다른 경우로 치는 것이다. 문제가 "방법이 몇 가지냐"라면 이건 보통 원하는 답이 아니다.

dp로 세기

n = 6
dp = [0] * (n + 1)
dp[0] = 1
coins = [1, 5, 10, 50, 100, 500]

for coin in coins:
    for i in range(coin, n + 1):
        dp[i] += dp[i - coin]

여기서는 2가 나온다. 1+5 와 5+1 이 하나로 세어진다.

무엇이 달라졌나

동전이 바깥 루프에 있다.

1원 차례가 끝나면 dp 에는 1원만 써서 만드는 방법이 들어 있다. 5원 차례로 넘어가면 거기에 5원을 쓰는 경우가 더해진다. 그리고 다시 1원 차례로 돌아가지 않는다.

동전을 한 번 지나가면 끝이므로 "1원 다음에 5원"은 세지만 "5원 다음에 1원"은 셀 기회가 없다. 순서가 자동으로 고정되고 조합만 남는다.

루프를 뒤집으면 반대가 된다.

for i in range(1, n + 1):
    for coin in coins:
        dp[i] += dp[i - coin]

금액이 바깥이면 금액 i 를 만들 때마다 모든 동전을 다시 고를 수 있다. 순서가 다른 것들이 따로 세어진다. 재귀 버전과 같은 답이 나온다.

두 겹 반복의 순서만 바꿨는데 세는 대상이 조합에서 순열로 바뀐다.

값 몇 개

금액이 커질수록 벌어진다. 순서를 구분하면 같은 동전 묶음이 늘어놓는 방법의 수만큼 부풀기 때문이다.

최댓값 문제와 다른 점

배낭 문제에서는 dp[i] = max(dp[i], dp[i - w] + v) 로 놓고 루프 순서를 별로 신경 쓰지 않았다. 최댓값은 같은 묶음을 몇 번 세든 답이 안 바뀌기 때문이다.

세는 문제는 다르다. 중복해서 세면 그대로 답이 틀린다. 같은 형태의 두 겹 반복인데 안에서 하는 게 max 냐 += 냐에 따라 순서가 답을 바꾼다.