[python3] 2225번: 합분해

풀이 일자: 23.02.17

난이도: [골드 V]

분류: [Math, DP]

문제 내용

 

 

문제 해결 흐름

1. 이것도 대표적인 DP문제 중 하나로 DP문제에서 가장 중요한 것은 점화식을 찾는 게 중요하다.

→ 한번 N과 K를 차례대로 조정해보면서 직접 경우의 수를 구해보자.

 

row: K(피연산자의 개수)/ col(만들어야 하는 합 & 0~N까지 피연산자로 사용가능한 수)

 

 K=2 N=3인 경우

0~3사이에 2개의 수를 가지고 3을 만들 수 있는 경우의 수는 0+3 / 1+2 / 2+1 / 0+3으로 경우의 수가 4이다.

 

이런식으로 계속 채워나가다보면 어떤 패턴을 발견해나갈 수 있는데 바로 현재 위치의 위쪽과 왼쪽의 수를 합하면 해당 경우의 수가 된다는 것을 확인할 수 있게 된다.

 

이를 코드로 옮겨본다면,

N, K = map(int, input().split());

dp = [[1 for i in range(N)] for j in range(K)];

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

print(dp[K-1][N-1]%1000000000);

=> 직접 해보면서 패턴을 찾는 방식으로 진행하였으며 좀더 생각해본다면 dp배열을 1차원으로만 정의하더라도 가능하다.

 

Time Complexity: O(N*K)

dp의 특성상 메모리제이션을 통한 답을 쌓아가면서 최종 정답을 내기 때문에 N*K만큼의 반복이 필요하다.

 

Space Complexity: O(N*K)

dp를 1차원으로 정의한다면 N이였겠지만 우선 이해와 편의를 위해 2차원으로 설정했기에 N*K만큼의 공간이 필요하다.

 

 

다른 해결 방식

1. 사실 dp를 1차원으로 만들어서 누적해서 처리하더라도 전혀 문제가 되지 않는다.

row: K(피연산자의 개수)/ col(만들어야 하는 합 & 0~N까지 피연산자로 사용가능한 수)

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

for _ in range(1, K):
    for j in range(1, N+1):
        dp[j] = dp[j-1] + dp[j];

print(dp[N]%1000000000);

=> 2차원으로 된다면 결국에는 이전의 데이터를 계속 이용한다는 것이고 이는 1차원으로도 풀 수 있다는 것을 의미한다.

 

2. 수학적으로 해결하는 방식이 존재한다.

→ 수학적인 관점으로 보자면 문제의 의미는 긴 탁자 뒤에 N개의 의자가 존재하고 0개 이상의 의자를 포함하는 그룹을 K개 만들어보자는 의미이다.

의자를 0개 이상 포함하는 K개의 그룹을 만들기 위해서는 (K-1)개의 칸막이가 필요할 것이다.

=> 김밥을 칼로 4개로 나누고 싶다면 몇 번 잘라야 하는지 생각해보면 쉽다.

그럼 다시 의자의 관점으로 돌아온다면 칸막이를 둘 수 있는 위치는 총 N+1개가 된다(의자의 맨 양끝도 가능하므로)

→ 그렇다면 N+1개의 칸막이를 둘 수 있는 자리 중 중복해서 K-1개의 칸막이를 둔다

→ 중복조합을 사용하면 된다.._N+1H_K-1 = _N+K-1C_K-1 = _N+K-1C_N

 

import math
n, k=map(int,input().split())
c=math.comb(n+k-1,n)%1000000000
print(c)

=> 다른 관점에서 본다면 수학적 방법으로도 충분히 가능하다.

 

 

문제 링크

https://www.acmicpc.net/problem/2225

2225번: 합분해