AUPC 2018 day3 A: Internet Protocol Address

問題

数字からなる文字列が与えられる。適当にピリオドを打ってvalidなIPアドレスにできるか。
IPアドレスは4つの0〜255の数の列。leading zeroはだめ。

制約

与えられる文字列は4文字以上12文字以下

方針

DPか全探索。どちらでも手間はかわらず。

ソースコード

int dp[20][20];
int main() {
	string s; cin >> s;
	dp[0][0] = 1;
	rep(i, s.size()) rep(j, 4){
		int num = 0;
		for(int k = i; k < i + 3 && k < s.size(); k++){
			num *= 10;
			num += s[k] - '0';
			if(num < 256){
				dp[k + 1][j + 1] += dp[i][j];
			}
			if(k == i && num == 0) break;
		}
	}
	cout << dp[s.size()][4] << endl;
	return 0;
}