#include <iostream>
#include <set>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string must, up, down;
int n;
int upsize;
int downsize;
int dp[1001][1001][2];
//bool upgo => True이면 다음에 up을 돌아야 한다는 것
int go(int idx, int mustidx,bool upgo) {
        if (mustidx == n) {
               return 1;
        }
        int& ret = dp[idx][mustidx][upgo];
        if (ret != -1) {
               return ret;
        }
        ret = 0;
        for (int i = idx + 1; i < upsize; ++i) {
               if (upgo && must[mustidx] == up[i]) {
                       ret += go(i, mustidx + 1, false);
               }
        }
        for (int i = idx + 1; i < downsize; ++i) {
               if (!upgo && must[mustidx] == down[i]) {
                       ret += go(i, mustidx + 1, true);
               }
        }
        return ret;
}
int main(void) {
        memset(dp, -1, sizeof(dp));
        cin >> must >> up >> down;
        int ans = 0;
        n = must.size();
        upsize = up.size();
        downsize = down.size();
        for (int i = 0; i < upsize; ++i) {
               if (must[0] == up[i])
                       ans += go(i, 1, false);
        }
        for (int i = 0; i < downsize; ++i) {
               if(must[0] == down[i])
                       ans += go(i,1,true);
        }
        cout << ans << endl;
        return 0;
}

저작자표시 비영리 변경금지
  • top-down은 다음에 해보자. 오랜만의 botton-up
  • 맨처음 case는 1,1,1 
  • 다음부터 cache[N][L][R]은 이전 정보를 받아온 다음 마지막 길이 1번건물을 어디에 놓냐만 생각하면 된다. 
  • cache[N - 1][L - 1][R] 이 식은 오른쪽에 1을 놓았다고 생각해서 이전정보에서 더해주는 것
  • cache[N - 1][L][R - 1] 이식은 반대로 왼쪽에 1을 놓았다고 생각한 것
  • cache[N - 1][L][R] * (N - 2) 이것은 양 끝을 제외하고 1을 놓았다고 생각한 것. 그래서 L과 R에 변화가 없다. 

#include <iostream>
using namespace std;
long long cache[101][101][101];
int main(void)
{
        int n, l, r;
        cin >> n >> l >> r;
        cache[1][1][1] = 1;
        for (int N = 2; N <= n; ++N) {
               for (int L = 1; L <= l; ++L) {
                       for (int R = 1; R <= r; ++R) {
                               cache[N][L][R] = cache[N - 1][L - 1][R] + cache[N - 1][L][R - 1] + cache[N - 1][L][R] * (N - 2);
                               cache[N][L][R] %= 1000000007;
                       }
               }
        }
        cout << cache[n][l][r] << endl;
        return 0;
}


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

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
vector<pair<int, int>> coin;
int cache[10001][101];
int n;
int money;
int go(int cash, int idx) {
        if (cash == 0) {
               return 1;
        }
        if (idx >= n) {
               return 0;
        }
        int& ret = cache[cash][idx];
        if (ret != -1) {
               return ret;
        }
        ret = 0;
        for (int i = 0; i <= coin[idx].second; ++i) {
               if (cash - (coin[idx].first * i) >= 0)
                       ret += go(cash - (coin[idx].first * i), idx + 1); // 다음 코인 쓰러 간다.
        }
        return ret;
}
int main(void)
{
        memset(cache, -1, sizeof(cache));
        cin >> money;
        cin >> n;
        for (int i = 0; i < n; ++i) {
               int a, b;
               cin >> a >> b;
               coin.push_back(make_pair(a, b));
        }
        cout << go(money, 0);
        return 0;
}

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

+ Recent posts

티스토리툴바