[2011] 합분해

2차원 DP 풀이

1. dp[0][i] = i번째 암호가 단독으로 문자로 치환되는 경우
2. dp[1][i] = i번째 암호가 i-1번째 암호 1과 함께 문자로 치환되는 경우
3. dp[2][i] = i번째 암호가 i-1번째 암호 2과 함께 문자로 치환되는 경우

일반적으로는 아래와 같은 점화식을 따릅니다.

1. dp[0][i] = dp[0][j - 1] + dp[1][j - 1] + dp[2][j - 1]
2. dp[1][i] = v[i-1]가 1일 때, dp[0][j - 1]
3. dp[1][i] = v[i-1]가 2일 때, dp[0][j - 1]

1번은 i-1길이의 암호에 새로 추가된 숫자 하나를 치환해서 만드는 암호 문자를 붙히는 경우입니다.
2번은 i-1길이의 암호 중 마지막 암호를 숫자로 바꾸고, 가장 뒤의 숫자 1과 새로운 숫자를 하나의 암호로 치환하는 경우입니다.
3번은 i-1길이의 암호 중 마지막 암호를 숫자로 바꾸고, 가장 뒤의 숫자 2과 새로운 숫자를 하나의 암호로 치환하는 경우입니다.

이렇게 진행하고 아래와 같은 예외 사항을 처리해주면 됩니다.

1. 0을 입력 받은 경우
2. 30, 40, 50, …, 90을 입력 받은 경우 : 30이상의 10의 배수
3. 100, 200, 300, …을 입력 받은 경우 : 100의 배수
4. 반드시 두 개의 숫자를 하나의 문자로 치환해야하는 경우 : 10과 20을 입력받은 경우, ex) 1020, 1012, 1054 등등

2차원 DP 코드

#include <iostream>
#include <string>
using namespace std;
int n;
int v[5001];
long long dp[3][5001];
long long mod = 1000000;
string s;
int main() {
	cin >> s;
	n = s.size();
	for (int i = 0; i < 5000; i++) {
		if (i < n) {
			v[i + 1] = s[i] - '0';
		}
		else {
			v[i + 1] = -1;
		}
	}
	
	dp[0][0] = 1;        
	for (int j = 1; j <= n; j++) {
		//일반적인 프로세스를 진행
		dp[0][j] += dp[0][j - 1]; dp[0][j] %= mod;
		dp[0][j] += dp[1][j - 1]; dp[0][j] %= mod;
		dp[0][j] += dp[2][j - 1]; dp[0][j] %= mod;

		if (v[j - 1] == 1) {
			dp[1][j] = dp[0][j - 1];
			dp[1][j] %= mod;
		}
		else if (v[j - 1] == 2 && v[j] <= 6) {
			dp[2][j] = dp[0][j - 1];
			dp[1][j] %= mod;
		}
		//예외 처리

		//현재 숫자가 0
		if (v[j] == 0) {
			//이전 숫자가 없는 경우 : 0으로 시작하는 암호
			if (j == 1) {
				printf("0\n");
				return 0;
			}
			else {
				//이전 숫자가 1 또는 2
				if (v[j - 1] == 1 || v[j - 1] == 2) {
					dp[0][j] = 0;
				}
				else { 
					//이전 숫자가 0 : 100, 200, 300, ...
					//이전 숫자가 3,~9 : 30,40,...,90
					printf("0\n");
					return 0;
				}
			}
			
		}
		
	}
	/*for (int i = 0; i < 3; i++) {
		for (int j = 1; j <= n; j++) {
			printf("%lld ", dp[i][j]);
		}
		printf("\n");
	}*/
	long long ans = 0;
	ans += dp[0][n]; ans %= mod;
	ans += dp[1][n]; ans %= mod;
	ans += dp[2][n]; ans %= mod;
	printf("%lld\n", ans);
	return 0;
}

1차원 DP 풀이

i번째 숫자는 단독으로 암호로 치환되거나 i-1번째 숫자와 함께(10~26) 암호로 치환될 수 있다.

코드

#include <iostream>
#include <string>
using namespace std;
int n;
int v[5001];
long long dp[5001];
long long mod = 1000000;
string s;
int main() {
	cin >> s;
	n = s.size();
	for (int i = 0; i < 5000; i++) {
		if (i < n) {
			v[i + 1] = s[i] - '0';
		}
		else {
			v[i + 1] = -1;
		}
	}
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		//한자리 암호 가능하면 1<= v[i] <=9
		if (i == 1 &&  v[i] == 0) {
			printf("0\n");
			return 0;
		}
		else if(v[i] != 0){
			dp[i] += dp[i - 1];
			dp[i] %= mod;
		}
		//두 자리 암호 가능하면 10<= v[i-1]*10+v[i]<=26
		if (10 <= v[i - 1] * 10 + v[i] && v[i - 1] * 10 + v[i] <= 26) {
			dp[i] += dp[i - 2];
			dp[i] %= mod;
		}
		//100,200,300,... 예외처리
		if (v[i - 1] == 0 && v[i] == 0) {
			printf("0\n");
			return 0;
		}
	}
	/*for (int i = 1; i <= n; i++) {
		printf("%lld ", dp[i]);
	}
	printf("\n");*/
	printf("%lld\n", dp[n]);
	return 0;
}

백준님 1차원 DP 풀이

s += “ “ + s; 이렇게도 쓰네요.

if (s[i-1] == '0') {
        continue;
    }

이 부분 때문에 100100를 입력하곡 dp를 찍어보니 아래와 같이 나옵니다.

1 1 0 0 0 0 0

#include <iostream>
using namespace std;
int d[5001];
int mod = 1000000;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    s = " " + s;
    d[0] = 1;
    for (int i=1; i<=n; i++) {
        int x = s[i] - '0';
        if (1 <= x && x <= 9) {
            d[i] += d[i-1];
            d[i] %= mod;
        }
        if (i==1) {
            continue;
        }
        if (s[i-1] == '0') {
            continue;
        }
        x = (s[i-1]-'0')*10 + (s[i]-'0');
        if (10 <= x && x <= 26) {
            d[i] += d[i-2];
            d[i] %= mod;
        }
    }
    cout << d[n] << '\n';
    return 0;
}