[BOJ 26660 // C++] A + B

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 26660번 문제인 A + B이다.
문제는 아래 링크를 확인하자

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

26660번: A + B

두 자연수의 '+'연산을 각 대응되는 자릿수의 합을 그대로 이어 쓰는 것으로 정의할 때 입력으로 주어진 수가 나오게 하는 식 A + B의 경우의 수를 구하는 문제이다.

 

처음서부터 i번째 자리 숫자까지의 수를 얻을 수 있는 경우의 수를 \(dp[i]\)라 할 때, 이 값은 "(\(dp[i-1]\) * ((한 자리로) i번째 자리 숫자를 얻을 경우의 수)"와 "(\(dp[i-2]\) * ((한 자리로) i-1~i번째 자리 숫자를 얻을 수 있는 경우의 수)"와 같이 얻을 수 있다는 점을 관찰하자.

 

위의 점화관계를 구현해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

string s; int slen;
ll dp[21];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	dp[0] = dp[1] = 1;

	cin >> s; s = "00" + s; slen = s.length();

	for (int i = 2; i < slen; i++) {
		dp[i] = dp[i - 1] * (s[i] - '0' + 1);
		ll tmp = stoll(s.substr(i - 1, 2));
		if (9 < tmp && tmp < 19) dp[i] += dp[i - 2] * (19 - tmp);
	}

	cout << dp[slen - 1];
}