[BOJ/2225] 합분해 - 풀이 및 코드

2225번: 합분해

문제

풀이

 문제를 단순하게 생각해서 푼다면 어떻게 풀 수 있을까요?

0부터 N까지의 숫자 중 K개를 더해 합을 N으로 만드는 경우의 수를 백트래킹 기법으로 완전탐색 할 수 있습니다. 완전탐색하게 되면 총 시간 복잡도는 O(2^n)만큼 걸리게 되기 때문에 완전탐색으로는 문제를 다항식 시간 내에 해결할 수 없습니다.

 

 그렇다면 문제가 원하는 경우의 수가 어떻게 생성되는지 알아보겠습니다.

만약 N을 3으로 고정하고 K가 1인 경우를 생각해보면 다음과 같은 결과를 얻을 수 있습니다.

 

숫자 1개를 사용해 숫자 0~N을 만드는 경우는 모두 1가지 방법 밖에 존재하지 않습니다.

 

 이번엔 K가 2인 경우에 1을 만드는 경우의 수를 구하는 과정을 자세히 살펴보겠습니다.

숫자 2개를 사용해 숫자 1을 만들려면 다음과 같이 구할 수 있습니다.

• 숫자 1에 0을 더하는 경우. 숫자 1개를 이용해 숫자 0을 만드는 경우의 수
• 숫자 0에 1을 더하는 경우. 숫자 1개를 이용해 숫자 1을 만드는 경우의 수
• 위 두 경우의 수를 더하면 숫자 2개를 이용해 숫자 1을 만드는 모든 경우의 수를 구할 수 있음.

패턴을 찾았습니다! 만약 이 부분에서 잘 이해가 되지 않는다면 다음과 같은 식을 통해 이해하실 수 있습니다.

 

이해가 어렵다면 색깔로 적힌 부분을 참조해주세요.

위와 같은 점화식을 활용하면 시간복잡도 O(K*N^2) 내에 문제를 풀 수 있습니다.

코드

코드 치팅은 BOJ 이용 제재 사유입니다.

위 풀이에선 2차원 배열을 이용해 풀었으나 1차원 배열을 이용해 풀 수도 있습니다. 1차원 배열 풀이는 2차원 배열 풀이와 동일하여 설명은 따로 하지 않겠습니다!

# 2차원 풀이

n, k = map(int, input().split())

dp = [[0 for _ in range(n+1)] for _ in range(k)]

# k가 1인 경우 0~N의 숫자를 만드는 경우의 수는 모두 1
for i, _ in enumerate(dp[0]):
    dp[0][i] = 1

for i in range(1, k):
    for j in range(n+1):
        for t in range(j+1):
            dp[i][j] += dp[i-1][t]

print(dp[-1][-1] % 1_000_000_000)

# 1차원 풀이
n, k = map(int, input().split())

# dp 테이블 갱신
dp = [1 for _ in range(n+1)]

for t in range(1, k):
    dp_c = dp[:]
    # i => 1 ~ n
    # i가 0일 때는 무조건 1개의 경우만 가능
    for i in range(1, n+1):
        temp = 0
        for j in range(i+1):
            temp += dp_c[i-j]
        dp[i] = temp

print(dp[n] % 1_000_000_000)

 

참고자료

이런 다이나믹 프로그래밍 문제를 냅색 알고리즘이라고 부릅니다.

https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

배낭 문제 - 위키백과, 우리 모두의 백과사전