[C언어] 백준 | 2225번 합분해

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

2225번: 합분해

 

안녕하세요. 

 

제 인생 첫 번째로 백준 골드 문제를 풀었습니다.

어제 프로그래밍 쪽지시험도 분반 1등하고 기분이 좋습니다.

 

그럼 설명하겠습니다.

 

n이 1일 경우

1 2 3 4 5 6 7 8 9 10  의 경우가 있는 것까지 계산하고

n이 2일 경우

1 3 6

n이 3일 경우

1 4 10 까지만 계산했습니다.

 

1 2 3

1 3 6

1 4 10  감이 오시나요?

 

arr[n][k] = arr[n - 1][k] + arr[n][k - 1] 로 나타나는 것을 알 수 있습니다.

1열은 모두 1입니다. n을 1개의 수로 나타낼 수 있는 방법은 n 밖에 없으니까요.



정수 오버플로우가 날 수 있으니 for문 내부에서 미리미리 나눠줬습니다. 

근데 실버3 dp문제 계단오르기를 못 풀겠네요..

#include <stdio.h>

int main(void) {
    int n, k;
    int arr[201][201];
    scanf("%d %d", &n, &k);
    arr[1][1] = 1;
    for(int i = 2; i < 201; i++) {
        arr[i][1] = 1;
        arr[1][i] = i;
    }
    for(int i = 2; i <= n; i++) {
        for(int j = 2; j <= k; j++) {
            arr[i][j] = (arr[i - 1][j] + arr[i][j - 1]) % 1000000000; 
        }
    }
    printf("%d", arr[n][k]);
}