백준 [2225] 합분해(Python3)

문제 링크 : https://www.acmicpc.net/problem/2225

2225번: 합분해

완전 탐색

0 ~ N까지 중복 포함 K개를 골라 합이 N인지 확인한다.
O(N ^ K) == O(200 ^ 200)이기 때문에 시간 초과다.

 

완전 탐색 최적화 - 탐색 횟수 줄이기

어떤 수 A가 있다면, 이 수는 아무튼 몇 개의 경우로 만들어진 수일 것이다.
각 수들이 각각 몇 개의 경우로 이루어질 수 있는지만 알 때
이 수들을 더해서 나온 B가 만들어질 수 있는 경우의 수는
B를 만드는데 사용된 수를 만들 수 있는 경우의 수를 더한 것과 같다.

 

완전 탐색 최적화 - DP

이차원 dp 테이블을 만든다. dp[K][N]
먼저, 각 수는 단일 수로 이루어지는 경우를 무조건 포함하기 때문에
dp[1][0] ~ dp[K][N] 의 값은 1로 한다.

 

3중 포문 풀이

먼저 1부터 K개 중 i개의 수를 고르는 경우를 고려한다.
여기서 선택할 수 있는 수는 0 ~ N 중 최대 탐색할 범위를 j라 한다.

이제 0 ~ j 사이의 수 하나를 k로 하고 dp[i 개의 수를 고름][현재 최대 탐색 범위인 j]에
k를 고르지 않고 만들 수 있는 경우인 dp[i - 1][j -k]를 더한다.

 

쉽게 말하자면, i개를 골라(1 <= i <= K) j를 만들 수 있고(0 <= j <= N)
j를 구성하는 어떤 수 k는 단일 형태로 사용한다 할 때(0 <= k <= j)
아무튼 j - k를 만들 수 있는 경우의 수를 더한다.

 

코드

N, K = map(int, input().split())
dp = [[0 for _ in range(N + 1)] for _ in range(K + 1)]

for i in range(0, N + 1):
    dp[1][i] = 1

for i in range(1, K + 1):
    for j in range(0, N + 1):
        for k in range(0, j + 1):
            dp[i][j] += dp[i - 1][j - k]

print(dp[K][N] % 1000000000)

 

2중 포문 풀이

예제의 케이스에 대해 처음부터 직접 써서 나열을 하는 중 놀라운 발견을 할 수 있었다.

i개를 고르고 j - 1개를 만드는 경우의 수 + i - 1개를 골라 j를 만드는 경우의 수를 합하면

i개를 골라 j가 되는 경우의 수가 된다는 것이었다.

 

여기에 대해 구현을해서 제출한 결과 AC를 맞았다.

 

코드

N, K = map(int, input().split())
dp = [[1] * (N + 1) for _ in range(K + 1)]

for i in range(0, N + 1):
    dp[1][i] = 1


for i in range(2, K + 1):
    for j in range(1, N + 1):
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 1000000000

print(dp[K][N] % 1000000000)