합분해 성공 풀이

시간 제한
메모리 제한
제출
정답
맞은 사람
정답 비율
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



#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n;
int money;
int arr[21];
int cnt;
int cache[10011][100];
int go(int sum,int index) {
       
       if (sum == 0) {
             return 1;
       }
       if (sum < 0) {
             return 0;
       }
       if (cache[sum][index] != -1) {
             return cache[sum][index];
       }
       cache[sum][index]++;
       int& ret = cache[sum][index];
       for (int i = index; i < n; ++i) {
             ret += go(sum - arr[i],i);
       }
       return ret;
}
int main(void)
{
       int t;
       cin >> t;
       while (t--) {
             memset(arr, 0, sizeof(arr));
             memset(cache, -1, sizeof(cache));
             cnt = 0;
             cin >> n;
             for (int i = 0; i < n; ++i) {
                    cin >> arr[i];
             }
             cin >> money;
             cout << go(money,0) << endl;
             
       }
       return 0;
}



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

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

[DP] 백준 2225 합분해 (개수가 주어진 문제)  (0) 2018.04.29
[DP] 백준 1965 상자넣기  (0) 2018.04.29
[EAZY] 백준 15624 피보나치 7  (0) 2018.04.02
[DP] 백준 11051 이항계수2  (0) 2018.04.02
[DP] 백준 1965 상자넣기  (0) 2018.04.02

#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 = 1000000007;
int main(void) {
       int ans = 0;
       int a = 1;
       int b = 1;
       for (int i = 0; i < n; ++i) {
              ans += a%mod + b%mod;
              a = ans;
              b = a;
       }
       cout << ans%mod;
       
       
       
       return 0;
}

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

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

[DP] 백준 1965 상자넣기  (0) 2018.04.29
[DP] 백준 9084 동전  (0) 2018.04.29
[DP] 백준 11051 이항계수2  (0) 2018.04.02
[DP] 백준 1965 상자넣기  (0) 2018.04.02
[EASY] 백준 2167 2차원 배열의 합  (0) 2018.04.02

이항계수 2 팩토리얼 값 미리 다이나믹으로 구해두고 나눠서 풀려고 했는데
나머지 연산이라 n은 본래 큰 값이지만 나머지는 n-m의 값보다 작을 수 있다. 해결할 방법이 지금 생각나지 않음.
#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;
int facto(int num) {
       cout << num << endl;
       if (num == 0) {
              return 1;
       }
       if (sche[num] != -1) {
              return sche[num];
       }
       sche[num] = ((num%10007) * (facto(num - 1)%10007))%10007;
       cout << sche[num] << endl;
       return sche[num];
}
int main(void) {
       memset(sche, -1, sizeof(sche));
       cin >> n >> m;
       if (n == m || m == 0) {
              cout << 1 << endl;
              return 0;
       }
       facto(n);
       cout << sche[n] / sche[n - m] / sche[m] ;
       
       return 0;
}


이게 해법 곱하기와 나누기 말고 합으로 해결 가능했다. 

#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;
int main(void) {
       
       cin >> n >> m;
       if (n == m || m == 0) {
              cout << 1 << endl;
              return 0;
       }
       cache[0][0] = cache[1][0] = cache[1][1] = 1;
       for (int i = 2; i <= n; ++i) {
              cache[i][0] = cache[i][i] = 1;
              for (int j = 1; j <= i-1; ++j) {
                     cache[i][j] = cache[i - 1][j - 1]%10007 + cache[i - 1][j]%10007;
              }
       }
       cout << cache[n][m]%10007;
       
       return 0;
}


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

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

[DP] 백준 9084 동전  (0) 2018.04.29
[EAZY] 백준 15624 피보나치 7  (0) 2018.04.02
[DP] 백준 1965 상자넣기  (0) 2018.04.02
[EASY] 백준 2167 2차원 배열의 합  (0) 2018.04.02
[DP] 백준 14916 거스름돈  (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;
}


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

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

[EAZY] 백준 15624 피보나치 7  (0) 2018.04.02
[DP] 백준 11051 이항계수2  (0) 2018.04.02
[EASY] 백준 2167 2차원 배열의 합  (0) 2018.04.02
[DP] 백준 14916 거스름돈  (0) 2018.04.02
[DP] 백준 9084 동전  (0) 2018.04.02


#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
#include <stack>
using namespace std;
int table[1001][1001];
int cache[1001][1001];
int dx[] = { 1,0,1 };
int dy[] = { 0,1,1 };
int n, m;
int i, j, x, y;
int main(void) {
       cin >> n >> m;
       for (int i = 0; i < n; ++i) {
              for (int j = 0; j < m; ++j) {
                     cin >> table[i][j];
              }
       }
       int t;
       cin >> t;
       while (t--) {
              cin >> i >> j >> x >> y;
              i -= 1;
              j -= 1;
              x -= 1;
              y -= 1;
              int sum = 0;
              for (int ii = i; ii <= x; ++ii) {
                     for (int jj = j; jj <= y; ++jj) {
                           sum += table[ii][jj];
                     }
              }
              cout << sum << endl;
       }
       return 0;
}


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

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

[DP] 백준 11051 이항계수2  (0) 2018.04.02
[DP] 백준 1965 상자넣기  (0) 2018.04.02
[DP] 백준 14916 거스름돈  (0) 2018.04.02
[DP] 백준 9084 동전  (0) 2018.04.02
[DP] 백준 동전 2 2294  (0) 2018.04.02

twofive 배열의 순서를 2,5 로 하냐, 5,2로 하냐에 차이가 있었다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
using namespace std;
int twofive[2] = { 5,2 };
int cache[100001];
int n;
int go(int money) {
       cout << money << '\n';
       if (money == 0) {
              return cache[money];
       }
       if (money < 0) {
              return 999999;
       }
       
       int& ret = cache[money];
       if (ret != -1) {
              return ret;
       }
       cache[money] = 999999;
       for (int i = 0; i < 2; ++i) {
              ret = min(ret, go(money - twofive[i]) + 1);
       }
       return ret;
}
int main(void) {
       memset(cache, -1, sizeof(cache));
       cin >> n;
       int ans = go(n) + 1;
       
       cout << (ans > 999990 ? -1 : ans) << endl;
       return 0;
}


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

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

[DP] 백준 1965 상자넣기  (0) 2018.04.02
[EASY] 백준 2167 2차원 배열의 합  (0) 2018.04.02
[DP] 백준 9084 동전  (0) 2018.04.02
[DP] 백준 동전 2 2294  (0) 2018.04.02
[DP] 백준 2011 암호코드  (0) 2018.01.02


         if (sum == 0) {
             return 1;
       }
       if (sum < 0) {
             return 0;
       }
       if (cache[sum][index] != -1) {
             return cache[sum][index];
       }
여기서 cache를 if 앞에 놔두면 런타임 에러가 났다. 

이 코드가 왜 성공하는지 100% 는 이해 못했지만 계속 하다보면 될 것 같다. 한발짝 나간 것 같다. 
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n;
int money;
int arr[21];
int cnt;
int cache[10011][100];
int go(int sum,int index) {
       
       if (sum == 0) {
             return 1;
       }
       if (sum < 0) {
             return 0;
       }
       if (cache[sum][index] != -1) {
             return cache[sum][index];
       }
       cache[sum][index]++;
       int& ret = cache[sum][index];
       for (int i = index; i < n; ++i) {
             ret += go(sum - arr[i],i);
       }
       return ret;
}
int main(void)
{
       int t;
       cin >> t;
       while (t--) {
             memset(arr, 0, sizeof(arr));
             memset(cache, -1, sizeof(cache));
             cnt = 0;
             cin >> n;
             for (int i = 0; i < n; ++i) {
                    cin >> arr[i];
             }
             cin >> money;
             cout << go(money,0) << endl;
             
       }
       return 0;
}



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

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

[EASY] 백준 2167 2차원 배열의 합  (0) 2018.04.02
[DP] 백준 14916 거스름돈  (0) 2018.04.02
[DP] 백준 동전 2 2294  (0) 2018.04.02
[DP] 백준 2011 암호코드  (0) 2018.01.02
[그래프] 백준 1987 알파벳  (0) 2017.12.14

최적화
안되는 경우는 money의 최댓값인 10000을 넘는 것을 리턴할 때 -1을 출력하도록 했다. 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
using namespace std;
int table[10001];
int cache[10001];
bool visited[10001];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int n;
int go(int money) {
       //cout << money << endl;
       if (money == 0) {
              return cache[money];
       }
       if (money < 0) {
              return 10001;
       }
       int& ret = cache[money];
       if (ret != -1) {
              return ret;
       }
       cache[money] = INT32_MAX;
       for (int i = 0; i < n; ++i) {
              ret = min(ret, 1 + go(money - table[i]));
       }
       return ret;
}
int main(void) {
       memset(cache, -1, sizeof(cache));
       int money;
       cin >> n >> money;
       for (int i = 0; i < n; ++i) {
              cin >> table[i];
       }
       int ans = go(money);
       cout << (ans>10000 ? -1 : ans+1) << endl;;
       return 0;
}


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

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

[DP] 백준 14916 거스름돈  (0) 2018.04.02
[DP] 백준 9084 동전  (0) 2018.04.02
[DP] 백준 2011 암호코드  (0) 2018.01.02
[그래프] 백준 1987 알파벳  (0) 2017.12.14
[그래프] 백준 5567 결혼식  (0) 2017.12.13

+ Recent posts

티스토리툴바