#include <iostream>

using namespace std;

int go(int a,int b){
    int sum = 0;
    if(a==0){
        return b;
    }
    for(int i=1;i<=b;++i){
        sum += go(a-1,i);
    }
    return sum;
}

int main(void){
    int t;
    cin >> t;
    while(t--){
        int a, b;
        cin >> a >> b;
        cout << go(a,b) << '\n';
    }
    return 0;
}


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

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

[BS] 백준 2343 기타레슨  (0) 2018.04.29
[BF] 완전탐색 1018 체스판 다시 칠하기  (0) 2018.04.29
[DP] 백준 2631 줄세우기  (0) 2018.04.29
[DP] 백준 5557 1학년  (0) 2018.04.29
[DP] 백준 10164 격자상의경로  (0) 2018.04.29

  • 아이디어가 중요 . 해서 그건 맨밑에 적겠다.
  • lis 구현할 줄 모른다 아직. 연습 
  • 재귀로 구현해보자
// boj 2631 줄세우기

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <limits.h>

using namespace std;

typedef long long ull;

int n;
int p[100001];
ull d[100001];

int main(void){

    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> p[i];
    }
    for (int i = 1; i <= n; ++i) {
        d[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (p[i] > p[j] && d[i] < d[j] + 1)
                d[i] = d[j] + 1;
        }
    }

    int max = -1;
    for (int i = 1; i <= n; ++i)
        if (max < d[i])
            max = d[i];

    cout << n - max << endl;
    
    return 0;
}




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

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

[BF] 완전탐색 1018 체스판 다시 칠하기  (0) 2018.04.29
[BF] 백준 2775 부녀회장이 될 테야  (0) 2018.04.29
[DP] 백준 5557 1학년  (0) 2018.04.29
[DP] 백준 10164 격자상의경로  (0) 2018.04.29
[DP] 백준 1915 가장 큰 정사각형 만들기  (0) 2018.04.29

  •   상한, 하한이 있는 문제 (sum은 중간에 0 에서 20 사이를 벗어나면 안되었다.)
  •   이것 때문에 dp 시작을 idx = 0, sum = 0 에서 하면 안되고 idx = 0 에서는 무조건 더하기만 가능했기 때문에 이를 구현하기 위해서 시작을 idx = 1, sum = tb1[0] 으로 해주어야 했다.
  •    1차원 cache로 구현하려고 오랫동안 고민했는데 ( 2차원으로 하는 문제란 걸 모르고 ) 2차원 배열로 sum의 경우까지 구분해 주어야 하는 것을 생각하지 못했었다. 질문 보기를 통해 알았다. idx 만으로 구분하기엔 뭔가 찜찜한 느낌은 있었는데 제대로 안 것 같다. 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <limits.h>

using namespace std;

typedef long long ull;

int n;
int tb1[111];
ull che1[110][21];

ull go(int idx, int sum){
    if(idx == n-1 && sum == tb1[idx]){
        return 1;
    }
    else if(idx == n-1){
        return 0;
    }
    if(sum > 20){
        return 0;
    }
    if(sum < 0){
        return 0;
    }

    ull& ret = che1[idx][sum];
    if(ret != -1){
        return ret;
    }
    ret = 0;
    ret = go(idx+1,sum+tb1[idx]) + go(idx+1,sum-tb1[idx]);
    return ret;
}

int main(void){
    memset(che1,-1,sizeof(che1));
    cin >> n;
    for(int i=0;i<n;++i){
        cin >> tb1[i];
    }
    cout << go(1,tb1[0]) << endl;
    
    return 0;
}




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

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

[BF] 백준 2775 부녀회장이 될 테야  (0) 2018.04.29
[DP] 백준 2631 줄세우기  (0) 2018.04.29
[DP] 백준 10164 격자상의경로  (0) 2018.04.29
[DP] 백준 1915 가장 큰 정사각형 만들기  (0) 2018.04.29
[DP] 백준 9461 파도반 수열  (0) 2018.04.29

+ Recent posts

티스토리툴바