Gidhub BE Developer

BOJ - 다리 놓기

2018-04-15
goodGid

Problem

Problem URL : 다리 놓기

Screenshots of Problem Explain

[1] Answer Code (18. 04. 15)

#include<iostream>
#include<cstring>
using namespace std;

int d[31][31];

int C(int n, int r) {
    if(n==r || r==0) return 1;
    if(d[n][r]>=0) return d[n][r];
    return d[n][r]=C(n-1,r)+C(n-1,r-1);
}

int main() {
    memset(d,-1,sizeof(d));
    int tc;
    cin >> tc;
    while (tc--) {
        int n, m;
        scanf("%d %d",&n,&m);
        printf("%d\n",C(m,n));
    }
}

[2] Answer Code (18. 04. 15)

#include<iostream>
using namespace std;

int main(){
    int tc;
    cin >> tc;
    
    while (tc--) {
        int a,b,n,r;
        
        a = b = 1;
        scanf("%d%d",&n,&r);
        
        for(int i=n-r+1; i<=n; i++)
            b = ( b * i ) / a++ ;
        
        printf("%d\n",b);
    }
    return 0;
}

Review

for(int i=n-r+1; i<=n; i++)
        b = ( b * i ) / a++ ;
  • 위 코드가 nCr 코드역할을 한다.
    대박 신기하다 !!!

Comments

Content