오늘의 문제
10942 팰린드롬?
2011 암호코드
2294 동전 2

10942 팰린드롬?

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, s, e, arr[2002], dp[2002][2002];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		for (int j = 0; j <= i; j++) dp[i][j] = 1;
	}

	for (int i = n - 1; i > 0; i--) {
		for (int j = i + 1; j <= n; j++) {
			if (arr[i] == arr[j]) {
				dp[i][j] = dp[i + 1][i + 1] & dp[i + 1][j - 1];
			}
		}
	}
	cin >> m;
	while (m--) {
		cin >> s >> e;
		cout << dp[s][e] << "\n";
	}
}

어제의 깨달음을 통해 DP 배열을 그리면서 문제를 풀었다. s번째 수부터 e번째 수가 팰린드롬을 이루는지 아닌지 판별하면 되기 때문에 dp[i][j]에 TF 값을 저장했다.

배열을 그리면 규칙이 금방 보인다. s번째 수부터 e번째 수가 팰린드롬을 이루는지 확인하기 위해선 dp[s+1][s+1]과 dp[s+1][e-1]이 팰린드롬인지를 확인하면 된다.

주의해야할 점은, dp[i][0] ~ dp[i][i]의 값을 모두 1로 셋팅해야한다는 점이다. dp[i][i]와 dp[i][[i] 또는 dp[i][[i+1]이 팰린드롬을 이루는지 판별하기 위해서이다.

2011 암호코드

코드

#include <bits/stdc++.h>
using namespace std;

string s;
long long dp[5002][2];

int main() {
	cin >> s;
	if (s[0] == '0') {
		cout << 0;
		return 0;
	}
	dp[0][0] = 1; dp[0][1] = 0;	
	for (int i = 1; i < s.size(); i++) {
		int b = s[i - 1] - '0', n = s[i] - '0';
		if (n == 0) {
			if (b > 2 || b == 0) {
				cout << 0;
				return 0;
			}
			else {
				dp[i][0] = dp[i - 1][0] % 1000000;
			}
		}
		else {
			if(b == 0) dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % 1000000;
			else if (b * 10 + n <= 26) {
				dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % 1000000;
				dp[i][1] = dp[i - 1][0] % 1000000;
			}
			else {
				if (s[i] == '0') {
					cout << 0;
					return 0;
				}
				dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % 1000000;
			}
		
		}
	}
	cout << (dp[s.size() - 1][0] + dp[s.size() - 1][1]) % 1000000;
}

잘 모르겠어서.. 모든 경우를 다 찾았다. 0에 주의를.
그러나 매우 깔끔한 해결 방법이 존재한다...

2294 동전 2

코드

#include <bits/stdc++.h>
using namespace std;

int n, k, arr[102], dp[10002];

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> arr[i];
	fill(dp, dp + 10002, 100002);

	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j == arr[i]) dp[j] = 1;
			else if (j > arr[i]) dp[j] = min(dp[j], dp[j - arr[i]] + dp[arr[i]]);
		}
	}
	cout <<( dp[k] >= 100002 ? -1 : dp[k]);
}