[ 백준 2225번 ] 합분해

by

1. 문제

2225호: 합성

첫 번째 줄은 결과를 1,000,000,000으로 나눈 나머지를 인쇄합니다.

'추천 관련글,

www.acmicpc.net

2. 해결

2차원 DP 문제이기 때문에 직관적으로 답을 찾기가 상당히 어려운 종류의 문제라고 할 수 있습니다.

따라서 재귀 방정식을 먼저 유도해 봅시다.

숫자 N을 K개의 정수 조합으로 변환하는 문제를 다시 조합하면 다음과 같이 생각할 수 있습니다.

dp(N)(K)는 N에서 K로 조합하는 방법의 수를 의미합니다.

예를 들어 N = 6이고 K = 4라고 가정합니다.

(_ , _ , _ , L) 4개의 숫자 조합의 마지막 자리 엘(0≤L≤6)으로 정하면 L의 값에 따라 다음 표의 경우의 수가 만들어지는 것을 알 수 있다.

엘 사례
0 dp(6)(3)
하나 dp(5)(3)
2 DP(4)(3)
삼 dp(3)(3)
4 dp(2)(3)
5 DP(1)(3)
6 dp(0)(3)

표는 (K – 1)개의 숫자를 사용하여 N에서 마지막 숫자 L을 빼서 값(N – L)을 형성하는 방법을 의미합니다.

마지막 숫자 L은 다른 숫자임이 보장되므로 모든 숫자가 다른 숫자를 만듭니다.

따라서 재귀 공식은 다음과 같이 요약할 수 있습니다.

그래도 한 가지 주의할 점은 dp(N)(1)은 항상 1이고 dp(1)(K)는 항상 K입니다.

오전. 물론 N을 숫자로 만드는 방법은 하나뿐이고, 1K 숫자를 만드는 것은 비트와 같이 K 위치에 1이 배치되는 횟수입니다.

dp(N)(K) = dp(0)(K – 1) + dp(1)(K – 1) + … + dp(N)(K – 1)

재귀 방정식을 기반으로 풀면 쉽게 풀 수 있지만, 재귀 방정식의 결과로 생성된 dp 배열에는 흥미로운 규칙이 숨겨져 있습니다.

엔↓ / 케이→ 하나 2 삼 4
하나 하나 2 삼 4
2 하나 삼 6 10
삼 하나 4 10 20

빨리 dp(N)(K) = dp(N – 1)(K) + dp(N)(K – 1) 이게 룰인데 이것도 누적 합계와 연관이 있으니 왜 적용되는지 알아보도록 할게요

3. 소스 코드

더보기

public class Main {

    static final int MOD = 1000000000;
    static int()() dp;

    public static void main(String() args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        dp = new int(N + 1)(K + 1);
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                if (j == 1) {
                    dp(i)(j) = 1;
                } else if (i == 1) {
                    dp(i)(j) = j;
                } else {
                    dp(i)(j) = (dp(i - 1)(j) + dp(i)(j - 1)) % MOD;
                }
            }
        }

        bw.write(dp(N)(K) + "");
        bw.close();
        br.close();
    }
}

GitHub – kwanik-kor/BOJ: Baekjoon Online Judge – 해결된 문제 및 전체 코드 설명

백준 온라인 판사 – 해결된 문제 설명 및 코드 완성 – GitHub – kwanik-kor/BOJ: 백준 온라인 판사 – 해결된 문제 설명 및 코드 완성

github.com