(회고) acmicpc 문제 1010 번: 다리 놓기

https://www.acmicpc.net/problem/1010 다리 놓기

문제가 n 개 중에 m 개 고르는 문제인데,
수학적 지식이 이제 없는 상태라 처음에는 단순히 전체 탐색을 시도

 #include <cstdio>  
 int A, B;  
 int num;  
 void find(int index, bool select, int count) {  
     if (index >= B)  
         return;  
     if (A == count) {  
         num++;  
         return;  
     }  
     if (B - index < A - count) {  
         return;  
     }  
     find(index + 1, true, count + 1);  
     find(index + 1, false, count);  
 }  
 int main(void) {  
     int N;  
     scanf("%d", &N);  
     while (N--) {  
         scanf("%d %d", &A, &B);  
         find(0, true, 1);  
         find(0, false, 0);  
         printf("%d\n", num);  
         num = 0;  
     }  
     return 0;  
 }  

시간 초과 발생

위 코드 이용해서 아래 테이블을 만들어서 규칙을 확인
=> 특정 i, j 값부터 이전 두 값(i, j-1 와 i-1, j-1)의 합

init() 함수에서 미리 값을 계산해 두고 입력시 바로 결과 출력하는 방식으로 변경해서 처리

 #define MAX 30  
 int table[MAX + 1][MAX + 1];  
 void init() {  
   for (int i = 1; i <= MAX; i++) {  
     for (int j = i; j <= MAX; j++) {  
       if (i == 1 || i == j - 1)  
         table[i][j] = j;  
       else if (i == j)  
         table[i][j] = 1;  
       else  
         table[i][j] = table[i][j - 1] + table[i - 1][j - 1];  
     }  
   }  
 }  

문제 풀고 short code 를 보면 머리가 나쁘면 손발이 고생이라는 게 느껴짐... -_-