백준 2011번: 암호코드

문제링크

https://www.acmicpc.net/problem/2011

2011번: 암호코드

풀이

• 숫자 두개 또는 하나를 알파벳 하나로 해석할 수 있다.
• $dp[cur][l]$ : cur 위치에서 l 길이를 한 글자로 볼 때 경우의 수

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  string s;
  cin >> s;

  vector<vector<int> > dp(s.size(), vector<int> (3, -1));

  function<int(int, int)> f = [&](int cur, int l) {
    if (cur > s.size()) return 0;

    auto& ret = dp[cur][l];
    if (ret != -1) return ret;

    if (s[cur] == '0') return ret = 0;

    auto num = stoi(s.substr(cur, l));
    if (num > 26 || num <= 0) return ret = 0;

    if (cur + l == s.size()) return ret = 1;

    return ret = (f(cur + l, 1) + f(cur + l, 2)) % 1000000;
  };

  cout << (f(0, 1) + f(0, 2)) % 1000000 << '\n';
}