76. 이항계수 [메모이제이션]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

5 3

 

출력예제 1

10

 

풀이 

- 조합을 구하는 문제 , 팩토리얼을 약간 변형하면 된다

- 공식이용 : nCr = n-1Cr-1 + n-1Cr

- 메모이제이션을 이용하는데 DFS로 구해놓은 값을 dy[n][r]에 저장한다

=> 미리 저장해 놓으면 해당 배열 값이 필요할 때 따로 구하지 않고 바로 return하면 된다(더 효율적임)

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int dy[21][21];

//76. 이항계수(조합)(메모이제이션)
//nCr=n-1Cr-1 + n-1Cr
int DFS(int n, int r){
    if(dy[n][r]>0) return dy[n][r]; //미리 구해놓은 것이 있으면 구하지 않고 배열에 잇는 값을 쓴다
    if(n==r || r==0) return 1;
    else return dy[n][r]=DFS(n-1, r-1)+DFS(n-1, r);
}


int main(){
    int n, r;
    scanf("%d %d", &n, &r);
    printf("%d\n", DFS(n, r));
    return 0;
}