백준알고리즘 이항계수를 풀어보았습니다.

먼저 1번인데요! 역시 기초 dp 및 재귀함수 알고리즘 이었습니다. 다 풀어버리고 빨리 어려운거 풀고싶어여



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <memory.h>
 
int dp[100];
 
int fec(int n)
{
    if(n==1||n==0)
    {    
        dp[n]=1;
        return dp[n];
    }
 
    if(dp[n]!=-1)
        return dp[n];
 
    dp[n]=n*fec(n-1);
 
    return dp[n];
}
 
int main(void)
{
    int n,r;
    memset(dp,-1,100);
    scanf("%d %d",&n,&r);
    printf("%d",fec(n)/(fec(r)*fec(n-r)));
    return 0;
}
cs


저작자표시

'알고리즘 > dynamic programming' 카테고리의 다른 글

백준알고리즘 피보나치 수  (0) 2017.03.13

Dynamic programming의 정석! 피보나치 수열을 dynamic programming로 구현 해 보았다.

사실 dp를 사용하지 않고 재귀로만 구현했더니 시간초과가 떠버렸다.

점화식은 f[n]=f[n-1]+f[n-2] 이다. 



알고리즘 스터디를 계기로 Dynamic programming 문제를여러가지 접해보았는데 어렵게 느껴져서 백준 알고리즘에서 쉬운 dp문제부터 차근차근 올라가려 한다.


다음에 올릴 땐 자바 연습할 겸 자바로 올려야지!


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <memory.h>
 
int dp[500];
 
int fibonacci(int n) {
    if(dp[n]!=-1)
        return dp[n];
    if (n==1||n==2) {
        return 1;
    } else {
        dp[n] = fibonacci(n-1) + fibonacci(n-2);
    }
    return dp[n];
}
 
int main(void)
{
    int x;
    memset(dp,-1,500);
    scanf("%d",&x);
    printf("%d",fibonacci(x));
    return 0;
}
cs


'알고리즘 > dynamic programming' 카테고리의 다른 글

백준알고리즘 이항계수  (0) 2017.03.26

+ Recent posts

티스토리툴바