#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int dp[1010];
 
int solve(int cnt)
{
    if(cnt < 0)
    {
        return 0;
    }
    else if(cnt == 0)
    {
        return 1;
    }
    
    if(dp[cnt] != 0)
    {
        return dp[cnt];
    }
 
    dp[cnt] = (solve(cnt-1) + solve(cnt-2) + solve(cnt-2)) % 10007;
    
    return dp[cnt];
}
 
int main(void)
{
//    freopen("B11727_input.txt", "r", stdin);
    
    cin >> N;
    
    cout << solve(N); 
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 11057] 오르막 수 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 10844] 쉬운 계단수 (DP) (C/C++)  (0) 2020.01.17
[백준 9095] 1, 2, 3 더하기 (DP) (C/C++)  (0) 2020.01.16
[백준 11726] 2xN 타일링 (DP) (C/C++)  (0) 2020.01.16
[백준 1463] 1로 만들기 (DP) (C/C++)  (0) 2020.01.16
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int dp[1010];
 
int solve(int cnt)
{
    if(cnt < 0)
    {
        return 0;
    }
    else if(cnt == 0)
    {
        return 1;
    }
    
    if(dp[cnt] != 0)
    {
        return dp[cnt];
    }
 
    dp[cnt] = (solve(cnt-1) + solve(cnt-2)) % 10007;
    
    return dp[cnt];
}
 
int main(void)
{
//    freopen("B11726_input.txt", "r", stdin);
    
    cin >> N;
    
    cout << solve(N); 
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 11057] 오르막 수 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 10844] 쉬운 계단수 (DP) (C/C++)  (0) 2020.01.17
[백준 9095] 1, 2, 3 더하기 (DP) (C/C++)  (0) 2020.01.16
[백준 11727] 2xN 타일링2 (DP) (C/C++)  (0) 2020.01.16
[백준 1463] 1로 만들기 (DP) (C/C++)  (0) 2020.01.16
#include <iostream>
#include <algorithm>
using namespace std;
 
int num;
int dp[1000010];
 
int solve(int n)
{
    if(n == 1)
    {
        return 0;
    }
    
    if(dp[n] != 99999999)
    {
        return dp[n];
    }
    
    if(n % 3 == 0)
    {
        dp[n] = min(dp[n], solve(n/3) + 1);
    }
    
    if(n % 2 == 0)
    {
        dp[n] = min(dp[n], solve(n/2) + 1);
    }
    
    if(n - 1 != 0)
    {
        dp[n] = min(dp[n], solve(n-1) + 1);
    }
    
    return dp[n];
}
 
int main(void)
{
//    freopen("B1463_input.txt", "r", stdin);
    
    cin >> num;
 
    for(int i = 0; i < 1000010; i++)
    {
        dp[i] = 99999999;
    }
    
    cout << solve(num);
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 11057] 오르막 수 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 10844] 쉬운 계단수 (DP) (C/C++)  (0) 2020.01.17
[백준 9095] 1, 2, 3 더하기 (DP) (C/C++)  (0) 2020.01.16
[백준 11727] 2xN 타일링2 (DP) (C/C++)  (0) 2020.01.16
[백준 11726] 2xN 타일링 (DP) (C/C++)  (0) 2020.01.16

+ Recent posts

티스토리툴바