놓을 수 있는 건 1번 경우와 같이 X, 왼, 오

이렇게 3개 다 놓으려면 가장 아랫줄이 빈칸이어야 한다.
 그 외의 경우에는 2개를 놓을 수 있다.
빈칸인 경우는 n-2와 같다. 왜냐하면 빈칸은 모든 경우에 한번씩 들어가므로 n-1을 만들기위해 사용한 n-2에서 하나씩 만들어 졌기 때문
그외의 경우의 개수는 n-1에서 n-2의 경우를 빼준 것과 같다. 그 경우는 *2씩 해주면 되므로 

마이너스의 모듈러 연산에서는 연산결과가 -가 될 수 있기 때문에 그 경우 mod를 더해줘야 한다. 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
#include <stack>
using namespace std;
typedef long long ll;
ll stb[10001]; // single table
ll sche[100001]; // single cache
int tb[1001][1001];
int cache[1001][1001];
int n,m;
const int mod = 9901;
int main(void) {
       
       cin >> n;
       sche[0] = 1;
       sche[1] = 3;
       for (int i = 2; i <= n; ++i) {
              
              int wow = sche[i - 1] - sche[i - 2];
              if (wow < 0) {
                     wow += mod;
              }
              
              sche[i] = (sche[i-2]*3)%mod  + (2*(wow))%mod;
       }
       cout << sche[n]%mod;
       
       
       return 0;
}


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 2096 내려가기  (0) 2018.04.29
[DP] 백준 9507 Generations of Tribbles  (0) 2018.04.29
[DP] 백준 2225 합분해 (개수가 주어진 문제)  (0) 2018.04.29
[DP] 백준 1965 상자넣기  (0) 2018.04.29
[DP] 백준 9084 동전  (0) 2018.04.29
 합분해 성공 풀이

시간 제한
메모리 제한
제출
정답
맞은 사람
정답 비율
2 초
128 MB
5062
2171
1634
42.630%

문제
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1≤N≤200), K(1≤K≤200)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
예제 입력 
20 2
예제 출력 
21




































합분해 문제

문제에서 어려웠던 점 

  • 어떻게 풀어야 하는지 전혀 파악이 안되었다. 

푸는 Logic

N이라는 숫자를 만들기 위해서 K개수의 숫자가 필요하다 

O + O + O .... + O = N

여기서 맨 마지막 수를 L 이라고 한다면 

O + O + O .... + O = N

d[k-1][n-L]     +  L

점화식은 이렇게 된다. 

L의 범위가 다음 topic 인데 

L은 N과 같을 때 가장 크고 0일 때 가장 작다. 

#include <iostream>

using namespace std;

int d[201][201];

int main(void)
{
    int n, k;
    cin >> n >> k;
    d[0][0] = 1;
    for (int i = 1; i <= k; ++i) {
        for (int j = 0; j <= n; ++j) {
            for (int l = 0; l <= j; ++l) {
                d[i][j] += d[i - 1][j - l];
                d[i][j] %= 1000000000;
            }
        }
    }
    cout << d[k][n];
    return 0;
}


















저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 9507 Generations of Tribbles  (0) 2018.04.29
[DP] 백준 1309 동물원  (0) 2018.04.29
[DP] 백준 1965 상자넣기  (0) 2018.04.29
[DP] 백준 9084 동전  (0) 2018.04.29
[EAZY] 백준 15624 피보나치 7  (0) 2018.04.02

처음에 ans = max(ans ... 부분을 for문을 안 돌리고 idx = 0 에서 시작하면 가장 큰 경우를 구할 수 있을 줄 알았다. 
하지만 idx >  0 에서 시작해서 더 큰 값을 구하는 경우가 존재한다. 

ex )
8 1 2 3 4 5 6 7 8 9 
idx = 0 부터하면 2
idx = 1 부터하면 9

#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
#include <stack>
using namespace std;
int stb[10001]; // single table
int scache[100001]; // single cache
int tb[1001][1001];
int cache[1001][1001];
int n;
int go(int idx) {
       
       if (scache[idx] != -1) {
              return scache[idx];
       }
       int& ret = scache[idx] = 1;
       for (int i = idx+1; i < n; ++i) {
              if (stb[idx] < stb[i]) {
                     ret = max(ret,go(i) + 1);
              }
       }
       return ret;
}
int main(void) {
       memset(scache, -1, sizeof(scache));
       cin >> n;
       for (int i = 0; i < n; ++i) {
              cin >> stb[i];
       }
       int ans = 0;
       for (int i = 0; i < n; ++i) {
              ans = max(ans, go(i));
       }
       
       cout << ans;
       return 0;
}


저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[DP] 백준 1309 동물원  (0) 2018.04.29
[DP] 백준 2225 합분해 (개수가 주어진 문제)  (0) 2018.04.29
[DP] 백준 9084 동전  (0) 2018.04.29
[EAZY] 백준 15624 피보나치 7  (0) 2018.04.02
[DP] 백준 11051 이항계수2  (0) 2018.04.02

+ Recent posts

티스토리툴바