BOJ G5 2225 합분해 JAVA

2225번: 합분해

---

문제 읽기

우선 처음에 딱 읽었을 때는 완탐 아니고서는 어떻게 풀지?? 싶었다. 중복을 허용하고, 순서가 바뀐 경우를 다르게 센다고 해서 중복 순열인가? 싶었지만 질문 게시판 살짝 보니 중복 조합이라고 하는데.. 잘 모르겠더라

 

그래서 일단은 예제를 가지고 고등학교 확통 시간을 떠올리며 직접 경우의 수를 세어봤다.

K = 2일 때는 음 그렇구나 했는데 K = 4인 걸 다 써보고 나니까 뭔가 규칙이 보였다..!! 물론 어떻게 나올 지는 모르지만, K = 4에는 K = 1인 것, K = 2인 것, K = 3인 것도 다 포함이 되어 있었다. 그래서 뭔가 DP적으로 접근한다면,, N이랑 K를 냅색처럼 이차원 배열로 나타낸다면 뭔가 보이지 않을까? 라는 생각이 들었고, 이 방식으로 접근해보았다.

 

---

문제 풀기

DP 테이블을 그려봤다.

예제의 답과 맞춰보기 위해 N = 1~6까지, K = 1~4까지 표를 채워보았다.

이렇게 경우의 수를 계산하면서 N = 1일 때, 2일 때까지 채웠더니 뭔가 규칙이 보였다. 해당 위치의 왼쪽 값과 위쪽 값을 더하니 해당 위치 값이 된 것이다.

그래서 이 다음부터는 계산하지 않고 그냥 규칙대로만 채웠더니 N = 6, K = 4일 때 값이 예제와 똑같이 나왔다.

즉, 이 규칙이 맞은 것이다 !!

 

그래서 다음과 같은 점화식을 도출할 수 있었다.

DP[n][k] = DP[n][k-1] + DP[n-1][k]

--init--
DP[n][1] = 1 (n = 1~N)
DP[1][k] = k (k = 1~K)

 

이를 코드로 작성하면 된다.

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_G5_2225_합분해 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        //init
        long[][] dp = new long[N+1][K+1];
        for (int n = 0; n < N+1; n++){
            dp[n][1] = 1;
        }
        for (int k = 0; k < K+1; k++){
            dp[1][k] = k;
        }

        //logic
        for (int n = 2; n < N+1; n++){
            for (int k = 2; k < K+1; k++){
                dp[n][k] = dp[n][k-1] + dp[n-1][k] % 1000000000;
            }
        }

        System.out.println(dp[N][K] % 1000000000);
    }
}

---

실수한 부분

범위

나는 최종 값이 10억으로 모듈러 한 값이라서 DP 배열을 long으로 선언하고 최종 값만 10억으로 모듈러 하여 출력했었다. 그런데 그렇게 하니 틀렸다고 나왔다.

혹시나 해서 DP에 값을 더해줄 때마다 모듈러 연산을 수행했는데 바로 맞다고 나왔다.

배열 원소 값이 long의 범위도 넘어가나 보다.. 헉..

• 틀렸을 때

• 맞았을 때

 

맞았을 때 값보다 틀렸을 때 값이 더 작아지는 거 보니 오버플로우가 발생한 것 같다.

 

이런 건 테스트 케이스로 꼭 확인해봐야겠다.