[C++] 백준 11051 -이항 계수 2

• 풀이 방법

• 메모이제이션

• 최종 코드

난이도 : 실버2

 

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

11051번: 이항 계수 2

 

풀이 방법

 

이항계수의 특징을 생각하면 쉽게 풀 수 있는 문제이다.

nCr = (n-1)Cr + (n-1)C(r-1)

 

mod 연산이 어떻게 되야하는지는 고민을 했다.

(a+b)%mod C = { (a%C) + (b%C) } % C

 

이 2가지의 공식을 이해했다면 코드 작성은 어렵지 않다.

하지만 시간 초과가 발생하였다.

이 방식이 재귀적이어서 이런 문제가 발생하는가 싶어 아예 코드를 갈아엎어야 하는지 혼란스러웠다. 그래도 속는셈 치고, 메모이제이션 방법으로 복잡도를 완화시켜보려고 했다.

 

 

메모이제이션

메모이제이션 (Memoization)은 컴퓨터 프로그램에서 자주 반복되는 계산의 결과를 저장함으로써 계산 속도를 높이는 기술이다. 이를 위해 이전에 수행한 계산 결과를 캐시(cache) 나 특정 저장소에 저장하고, 이후 동일한 계산을 수행할 때는 특정 저장소에서 결과를 반환하여 계산 시간을 단축시킨다.

 

특정 캐시를 나는 2차원 배열로 구현하여 이미 계산한 nCr 값은 계산하지 않도록 만들었다.

결과는 성공이었다.

 

 

원래 이 방법에 대해 알고 있었지만 결과를 크게 바꿔주는 방법은 아니라고 생각했다.
하지만 이번 경험으로 메모이제이션으로 시간복잡도를 줄이려는 노력도 해봐야겠다는 생각을 했다.
특히 재귀적으로 진행되는 알고리즘 경우에는 같은 함수가 여러 번 반복되기 때문에 메모이제이션이 특히 효율적인 방법이 될 수 있다.

 

최종 코드

#include <iostream>

int b[1001][1001];

int check(int n, int k){
    if(k == 0 || n == k){
        b[n][k] = 1;
        return 1;
    }
    
    if(b[n][k] != 0){
        return b[n][k];
    }
    
    int t1 = check(n-1,k)%10007;
    int t2 = check(n-1,k-1)%10007;
    b[n][k] = t1+t2;
    return b[n][k];
}

int main(void){
    int N,K;
    scanf("%d %d", &N, &K);
    
    int result = check(N,K);
    printf("%d\n", result%10007);
}