#include <iostream>
#include <algorithm>
using namespace std;
 
#define MOD 1000000000
 
int N;
int sum;
long long dp[110][11];
 
int solve(int cnt, int num)
{
    if(cnt == 1)
    {
        return num == 0 ? 0 : 1;
    }
    
    if(dp[cnt][num] != 0)
    {
        return dp[cnt][num];
    }
 
    if(num == 0)
    {
        dp[cnt][num] = solve(cnt-1, num+1) % MOD;
    }
    else if(num == 9)
    {
        dp[cnt][num] = solve(cnt-1, num-1) % MOD;
    }
    else
    {
        dp[cnt][num] = (solve(cnt-1, num-1) + solve(cnt-1, num+1)) % MOD;
    }
    
    return dp[cnt][num];
}
 
int main(void)
{
//    freopen("B10844_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i <= 9; i++)
    {
        sum = (sum + solve(N, i)) % MOD;        
    }
    
    cout << sum;
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 2193] 이친수 (DP) (C/C++)  (0) 2020.01.17
[백준 11057] 오르막 수 (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
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int T;
int num;
int dp[20];
 
int solve(int n)
{
    if(n < 0)
    {
        return 0;
    }
    else if(n == 0)
    {
        return 1;
    }
    
    if(dp[n] != 0)
    {
        return dp[n];
    }
    
    dp[n] = solve(n-1) + solve(n-2) + solve(n-3);
    
    return dp[n];
}
 
int main(void)
{
//    freopen("B9095_input.txt", "r", stdin);
    
    cin >> T;
 
    for(int i = 1; i <= T; i++)
    {
        cin >> num;    
        
        cout << solve(num) << endl;
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 11057] 오르막 수 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 10844] 쉬운 계단수 (DP) (C/C++)  (0) 2020.01.17
[백준 11727] 2xN 타일링2 (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) + 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
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
 
vector<int> a; // left
vector<int> b; // right
int dp[2010][2010] = {0};
 
int solve(int leftIdx, int rightIdx)
{
    if(leftIdx == a.size() || rightIdx == b.size())
    {
        return 0;
    }
    
    if(dp[leftIdx][rightIdx] != -1)
    {
        return dp[leftIdx][rightIdx];
    }
    
    // 1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
    dp[leftIdx][rightIdx] = max(solve(leftIdx+1, rightIdx), solve(leftIdx+1, rightIdx+1));
    
    // 2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
    if(a[leftIdx] > b[rightIdx])
    {
        dp[leftIdx][rightIdx] = max(dp[leftIdx][rightIdx], solve(leftIdx, rightIdx+1) + b[rightIdx]);
    }
    
    return dp[leftIdx][rightIdx];
}
 
int solution(vector<int> left, vector<int> right) 
{
    a = left;
    b = right;
    
    memset(dp, -1, sizeof(dp));
    
    int answer = solve(0, 0); 
    
    return answer;
}
cs
저작자표시 (새창열림)

'Programmers > Level 4' 카테고리의 다른 글

[프로그래머스 4] 징검다리 (C/C++) (★★★)  (0) 2020.04.26
[프로그래머스 4] 4단 고음 (C/C++) (★★★)  (0) 2020.03.11
[프로그래머스 4] 블록 게임 (C/C++) (★★)  (0) 2020.03.05
[프로그래머스 4] 도둑질 (C/C++) (★)  (0) 2020.01.15
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> money) 
{
    int dp1[1000010] = {0};
    int dp2[1000010] = {0};
    
    // 출발점 : 첫번째 집
    dp1[0] = money[0];
    dp1[1] = money[0];
    for(int i = 2; i < money.size()-1; i++)
    {
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i]);
    }
    
    // 출발점 : 두번째 집
    dp2[1] = money[1];
    for(int i = 2; i < money.size(); i++)
    {
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i]);
    }
    
    return max(dp1[money.size()-2], dp2[money.size()-1]);
}
cs
저작자표시 (새창열림)

'Programmers > Level 4' 카테고리의 다른 글

[프로그래머스 4] 징검다리 (C/C++) (★★★)  (0) 2020.04.26
[프로그래머스 4] 4단 고음 (C/C++) (★★★)  (0) 2020.03.11
[프로그래머스 4] 블록 게임 (C/C++) (★★)  (0) 2020.03.05
[프로그래머스 4] 카드게임 (C/C++) (★★)  (0) 2020.01.15
#include <string>
#include <vector>
using namespace std;
 
int solution(int m, int n, vector<vector<int>> puddles) 
{
    int dp[110][110] = {0}; // dp[n][m]
    
    // 세로 1로 표시
    for(int i = 1; i <= n; i++)
    {
        dp[i][1] = 1;
    }   
        
    // 가로 1로 표시
    for(int i = 1; i <= m; i++)
    {
        dp[1][i] = 1;
    }
    
    // 웅덩이 -1로 표시
    for(int i = 0; i < puddles.size(); i++)
    {
        dp[puddles[i][1]][puddles[i][0]] = -1;
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            // 집
            if(i == 1 && j == 1)
            {
                continue;
            }
            
            // 웅덩이
            if(dp[i][j] == -1)
            {
                dp[i][j] = 0;
            }
            else
            {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;  
            }
        }
    }
    
    return dp[n][m];
}
cs
저작자표시 (새창열림)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 입국 심사 (C/C++)  (0) 2020.01.27
[프로그래머스 3] 예산 (C/C++)  (0) 2020.01.26
[프로그래머스 3] 타일 장식물 (C/C++)  (0) 2020.01.11
[프로그래머스 3] 정수 삼각형 (C/C++)  (0) 2020.01.11
[프로그래머스 3] 저울 (C/C++) (★)  (0) 2020.01.11

+ Recent posts

티스토리툴바