#include <iostream>
#include <cstring> //memset
 
using namespace std;
const int MOD = 1000000000;
int cache[10][101]; //cache[digit][length], digit으로 시작하는 숫자, length는 길이
 
int dp(int digit, int length)
{
    if (digit < 0 || digit > 9) //한자리수만 가능
        return 0;
 
    if (cache[digit][length] != -1)
        return cache[digit][length];
 
    //다음 수를 하나 작은 수 혹은 하나 큰 수로
    return cache[digit][length] = (dp(digit - 1, length - 1) + dp(digit + 1, length - 1)) % MOD;
}
 
int main(void)
{
    int N;
    cin >> N;
 
    if (N < 1 || N > 100)
        exit(-1);
 
    memset(cache, -1, sizeof(cache));
 
    for (int i = 0; i < 10; i++)
        cache[i][1] = 1; //초기값(1~9까지는 1씩)
 
    int sum = 0;
 
    for (int i = 1; i <= 9; i++)
    {
        sum += dp(i, N); //0으로 시작하는 숫자는 없으므로 1부터
        sum %= MOD; //이 코드를 작성하지 않으면 틀렸다고 나옵니다.
    }
 
    cout << sum << endl;
 
    return 0;
}
cs

'백준' 카테고리의 다른 글

[C++] 백준(BAEKJOON) 1005  (0) 2019.03.23
[C++] 백준(BAEKJOON) 2579  (0) 2019.03.18
[C++] 백준(BAEKJOON) 1463  (0) 2019.03.14
[C++] 백준(BAEKJOON) 1149  (0) 2019.03.13
[C++] 백준(BAEKJOON) 1003  (0) 2019.03.13
 
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
     
    int t;
    int n, k, endPoint;
    int delay[1001];
    int path[1001][1001];
    int cache[1001];
    
    int dp(int x) {
        if (cache[x] != 0) 
            return cache[x];
        
        int result = 0;
        for (int i = 1; i <= n; i++) {
            if (path[x][i]) {
                result = max(result, dp(i));
            }
        }
        return cache[x] = result + delay[x];
    }
     
    int main() {
        cin >> t;
        while (t--) {
            cin >> n >> k;
            
            for (int i = 1; i <= n; i++) {
                cin >> delay[i];
            }
            
            for (int i = 0; i < k; i++) {
                int a, b;
                cin >> a >> b;
                path[b][a] = true;
            }
            
            cin >> endPoint;
            cout << dp(endPoint) << '\n';
            
            memset(delay, 0, sizeof(delay));
            memset(path, 0, sizeof(path));
            memset(cache, 0, sizeof(cache));
        }
        return 0;
    }
 
cs


'백준' 카테고리의 다른 글

[C++] 백준(BAEKJOON) 10844  (0) 2019.08.16
[C++] 백준(BAEKJOON) 2579  (0) 2019.03.18
[C++] 백준(BAEKJOON) 1463  (0) 2019.03.14
[C++] 백준(BAEKJOON) 1149  (0) 2019.03.13
[C++] 백준(BAEKJOON) 1003  (0) 2019.03.13
 
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int n;
    int stair[301];
    int cache[301];
     
    int dp (int x){
        if(x==0)
            return 0;
            
        if(x==1)
            return stair[0];
        
        if(x==2)
            return stair[0]+stair[1];
            
        if(x==3)
            return max(stair[0]+stair[2],stair[1]+stair[2]);
        
        if(cache[x] != 0) 
            return cache[x];
        
        return cache[x] = max(dp(x-2), dp(x-3)+stair[x-2]) + stair[x-1];
    }
     
    int main() {
        cin >> n;
        
        for (int i = 0; i < n; i++) {
            cin >> stair[i];
        }
        
        cout << dp(n);
     
        return 0;
    }
 
cs


'백준' 카테고리의 다른 글

[C++] 백준(BAEKJOON) 10844  (0) 2019.08.16
[C++] 백준(BAEKJOON) 1005  (0) 2019.03.23
[C++] 백준(BAEKJOON) 1463  (0) 2019.03.14
[C++] 백준(BAEKJOON) 1149  (0) 2019.03.13
[C++] 백준(BAEKJOON) 1003  (0) 2019.03.13


#include <stdio.h>
using namespace std;
 
int n;
int cache[10000001];
 
int dp(int x){
    if(x == 1)
        return 0;
    
    if(cache[x] > 0)
        return cache[x];
    
    cache[x] = dp(x-1) + 1;
    
    if(x%2 == 0){
        int temp = dp(x/2) + 1;
        if(cache[x] > temp)
            cache[x] = temp;
    }
    
    if(x%3 == 0){
        int temp = dp(x/3) + 1;
        if(cache[x] > temp)
            cache[x] = temp;
    }
    
    return cache[x];
}
 
int main(){
    scanf("%d", &n);
    
    printf("%d", dp(n));
    
    return 0;
}

cs


'백준' 카테고리의 다른 글

[C++] 백준(BAEKJOON) 1005  (0) 2019.03.23
[C++] 백준(BAEKJOON) 2579  (0) 2019.03.18
[C++] 백준(BAEKJOON) 1149  (0) 2019.03.13
[C++] 백준(BAEKJOON) 1003  (0) 2019.03.13
[C++] 백준(BAEKJOON) 11726  (0) 2019.03.13


#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n;
int cost[1001][3];
int cache[1001][3];
 
int dp(int home_index, int color_index)
{
    if(home_index >= n)
        return 0;
 
    if(cache[home_index][color_index])
        return cache[home_index][color_index];
 
    int m = -1;
 
    for(int i=0;i<3;i++)
        if(i != color_index)
        {
            if( m == -1 )
                m = cost[home_index][color_index] + dp(home_index + 1, i);
            else
                m = min(m, cost[home_index][color_index] + dp(home_index + 1, i));
        }
 
    cache[home_index][color_index] = m;
    
    return m;
}

int main()
{
    scanf("%d", &n);
 
    for(int i=0;i<n;i++)
    {
        scanf("%d", &cost[i][0]);
        scanf("%d", &cost[i][1]);
        scanf("%d", &cost[i][2]);
    }
 
    int m = dp(0, 0);
    m = min(m, dp(0, 1));
    m = min(m, dp(0, 2));
 
    printf("%d", m);
 
    return 0;
}

cs


'백준' 카테고리의 다른 글

[C++] 백준(BAEKJOON) 2579  (0) 2019.03.18
[C++] 백준(BAEKJOON) 1463  (0) 2019.03.14
[C++] 백준(BAEKJOON) 1003  (0) 2019.03.13
[C++] 백준(BAEKJOON) 11726  (0) 2019.03.13
[C++] 백준(BAEKJOON) 1932  (0) 2019.03.13


#include <iostream>
 
int n;
int cache[41];
 
int fibonacci(int x) {
    if (x == 0) 
        return 0;
        
    if (x == 1 || x == 2) 
        return 1;
        
    if(cache[x])
        return cache[x];
        
    return cache[x] = fibonacci(x - 2) + fibonacci(x - 1);
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; ++i) {
        int number;
        scanf("%d", &number);
        if (number == 0) 
            printf("1 0\n");
        else 
            printf("%d %d\n", fibonacci(number - 1), fibonacci(number));
    }
 
    return 0;
}

cs


'백준' 카테고리의 다른 글

[C++] 백준(BAEKJOON) 2579  (0) 2019.03.18
[C++] 백준(BAEKJOON) 1463  (0) 2019.03.14
[C++] 백준(BAEKJOON) 1149  (0) 2019.03.13
[C++] 백준(BAEKJOON) 11726  (0) 2019.03.13
[C++] 백준(BAEKJOON) 1932  (0) 2019.03.13


#include <stdio.h>
 
int n;
int cache[1001];
 
int dp (int x){
    if(x==1)
        return 1;
    
    if(x==2)
        return 2;
    
    if(cache[x] != 0) 
        return cache[x];
    
    return cache[x] = (dp(x-1) + dp(x-2)) % 10007;
}
 
int main(void){
    scanf("%d", &n);
    
    printf("%d", dp(n));
    
    return 0;
}


cs


'백준' 카테고리의 다른 글

[C++] 백준(BAEKJOON) 2579  (0) 2019.03.18
[C++] 백준(BAEKJOON) 1463  (0) 2019.03.14
[C++] 백준(BAEKJOON) 1149  (0) 2019.03.13
[C++] 백준(BAEKJOON) 1003  (0) 2019.03.13
[C++] 백준(BAEKJOON) 1932  (0) 2019.03.13


#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
 
int n;
int triangle[501][501];
int cache[501][501];
 
int dp(int y, int x){
    if(y == n-1)
        return triangle[y][x];
        
    int& ret = cache[y][x];
    
    if(ret != -1)
        return ret;
        
    return ret = max(dp(y+1, x), dp(y+1, x+1)) + triangle[y][x];
}
 
int main(void){
    scanf("%d", &n);
    
    for (int i = 0; i<n; i++){
        for (int j = 0; j <= i; j++){
            scanf("%d", &triangle[i][j]);
        }
    }
    
    memset(cache, -1, sizeof(cache));
    
    printf("%d", dp(0, 0));
    
    return 0;
}

cs


'백준' 카테고리의 다른 글

[C++] 백준(BAEKJOON) 2579  (0) 2019.03.18
[C++] 백준(BAEKJOON) 1463  (0) 2019.03.14
[C++] 백준(BAEKJOON) 1149  (0) 2019.03.13
[C++] 백준(BAEKJOON) 1003  (0) 2019.03.13
[C++] 백준(BAEKJOON) 11726  (0) 2019.03.13

+ Recent posts

티스토리툴바