BOJ12105 123456789찾기(C++)

---

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

태그 : dp, 수학, kmp

---

사고 과정

일단 문자열이 나타나는지 10000자리에 대해 판별해야 한다.

kmp에 취소선을 그은 것은, kmp가 생각이 나긴 하지만

(n - m) * m에 대해서도 문제없이 1초 안에 돌 것이라고 생각했다.

사실상 메인은 1~9를 판별하는 것이였다.

---

관찰

개인적으로 왜 태그에 수학이 없는지 모르겠다. 푼 사람이 적어서인 것 같긴 한데,

굳이 따지면 문자열보다도 수학이 들어가있어야하지 않나 싶다.

풀고 나니 별거 아닌 관찰같긴 하다... 왜 못떠올렸을까

인덱스를 곱했을 때 1~9의 LCM인 2520이 나오면 된다.

이걸 떠올렸다면(난 못했지만) 문자열의 0번(1이겠지만)인덱스부터

$2^{3}$ x $3^{2}$ x $5$ x $7$의 형태로 표현해주면 된다. 저 곱이 2520이고,

2가 3개 이상, 3이 2개 이상, 5가 1개, 7이 1개 이상 나타나는 모든 조합을 구해주면 된다.

가중치를 12, 4, 2, 1로 두고 이진수 표현하는 것 처럼 구하면 된다.

2의 가중치가 12인건 2를 제외한 세 수가 3x2x2 = 12가지로 표현되기 때문이다. 3도 마찬가지

2가 1개, 3이 2개, 5 1개, 7 1개 쓰였다면

12x1 + 4x2 + 2x1 + 1x1 = 23으로 표현하면 된다.

---

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

#define MOD 1000000007
typedef long long ll;

string p, s;
ll ans;

bool arr[10000];
ll dp[10001][48];

//12 / 4 / 2 / 1

int getCnt(int n, int div) {
	int cnt = 0;
	while (n && n % div == 0) {
		n /= div;
		cnt++;
	}
	return cnt;
}

void solve() {
	int pL = p.length();
	int sL = s.length();

	for (int i = 0; i <= sL - pL; ++i) {
		string str;
		for (int j = i; j < i + pL; ++j) {
			str += s[j];
		}
		if (str == p) {
			arr[i] = 1;
		}
	}

	if (arr[0]) {
		dp[0][0]++;
	}

	for (int i = 1; i <= sL - pL; ++i) {
		for (int j = 0; j < 48; ++j) {
			dp[i][j] = dp[i - 1][j];
		}

		if (arr[i]) {
			int cnt2 = min(3, getCnt(i + 1, 2));
			int cnt3 = min(2, getCnt(i + 1, 3));
			int cnt5 = min(1, getCnt(i + 1, 5));
			int cnt7 = min(1, getCnt(i + 1, 7));

			int next = 12 * cnt2 + 4 * cnt3 + 2 * cnt5 + cnt7;
			dp[i][next]++;

			for (int j = 0; j < 48; ++j) {
				int cpy = j;
				int prev2 = cpy / 12;
				cpy %= 12;
				int prev3 = cpy / 4;
				cpy %= 4;
				int prev5 = cpy / 2;
				cpy %= 2;
				int prev7 = cpy;
				next = 12 * min(prev2 + cnt2, 3) + 4 * min(prev3 + cnt3, 2) + 2 * min(prev5 + cnt5, 1) +  min(prev7 + cnt7, 1);
				
				dp[i][next] += dp[i - 1][j];
				dp[i][next] %= MOD;
			}
		}
	}
	ans = dp[sL - pL][47];
}

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

	cin >> p >> s;

	solve();

	cout << ans;
}

---