[백준] (Swift) 2225번 - 합분해 (dp, 2차원 규칙, 스위프트 풀이)

문제 링크

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

2225번: 합분해

 

풀이 IDEA

규칙을 찾다가 2차원배열로 풀어야한다는 생각을 미처 하지 못해서 인터넷을 참고했다. dp 도 다양한 유형을 풀며 어떤 상황일 경우 어떻게 접근해야하는지 감을 익혀야하는 것 같다.

• 규칙찾기가 힘들었다.
• 이런 문제가 나오면 2차원으로 풀자.
• k개를 더해서 n을 만드는 경우의 수를 배열로 넣으면 된다.
• 2차원 배열일 경우 표를 그리면서 규칙을 찾아나서면 된다.
• 생각보다 간단한 규칙이 있다.
• dp는 무조건 규칙부터!

규칙을 설명해보겠다. 우선 위에서 적은것 처럼 k개의 수를 더해서 n을 만들자! 라는 맥락으로 시작했고 이를 dp[k][n] 배열에 넣었다. 그리고 예제 2번 으로 주어진 예시가 규칙을 찾기에 적절한 것 같아서, n=6, k=4 를 기반으로 규칙을 찾아보았다.

규칙을 따라 표를 만들어보면, 우선 1차적으로 이렇게 나온다. 숫자 1개를 갖고 1,2,3,4,5,6 을 만들 수 있는 경우의 수는 각각 1개이며, 숫자 0을 만들기 위한 경우의수도 모두 1개씩이다. (0+0+0=0 이니까!) 이를 모두 적어 둔 뒤, 상대적으로 계산하기 쉬운 2 를 먼저 경우의수를 적어보자.

표를 채워 나가다 보니, 위와 같은 규칙을 발견했다. 상대적으로 규칙을 찾기 노란색 부분부터 경우의 수를 따져보니, [k-1][n] + [n][k-1] 번째에 있는 수를 더해주면 노란색 값이 나온다는 것을 알 수 있었다. 그렇게 계산산하다보면, 최종적인 값 숫자 4개를 더해서 6을 만들 수 있는 경우의수는 84로, 예제와 동일한 결과값이 나온다는 것을 알 수 있었다.

이렇게 규칙을 찾았으니 이제 점화식을 구해보자. 처음 생각하기에는 매우 복잡했지만, 이렇게 규칙을 찾아놓으니 비교적 이번 문제의 점화식은 쉽다. 원하는 값의 위+옆 값을 더해주면 되니 말이다. 그렇게 구한 점화식은 아래와 같다.

dp[k개의수로][n만들기] = dp[k-1][n] + dp[k][n-1]

이렇게 만든 점화식을 소스코드로 그대로 구현하면, 아래와 같다.

 

소스코드

아 그리고, for 문에서 k는 1부터 들어갈 수 있기 떄문에 1부터 진행해주었다. (숫자를 0개 더한다는 것은 말이 안되기 때문!) 더불어서, n=0일 경우에는 별도의 계산없이 모든 경우읜 수가 1이므로, if 문을 활용하여 1을 넣어주었다.

let nk = readLine()!.split(separator: " ").map { Int(String($0))! }
var dp = Array(repeating: Array(repeating: 0, count: nk[0]+1), count: nk[1]+1)
// dp[k][n] k개 더해서 값이 n

for k in 1..<nk[1]+1 {
    for n in 0..<nk[0]+1 {
        if n == 0 {
            dp[k][0] = 1
        } else {
            dp[k][n] = (dp[k-1][n]+dp[k][n-1]) % 1000000000
        }
    }
}

print(dp[nk[1]][nk[0]])