백준 23325: 마법천자문

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

23325번: 마법천자문

 

전형적인 DP문제다.

요즘 너무 DP만 푸는거 같긴 하다.

진짜 비정상

 

 

계단 문제랑 비슷한 원리다.

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

2579번: 계단 오르기

 

문자열 s의 0번째부터 i번째 문자까지 보았을 때 답을 dp[i]라고 둔다.

i번째 문자까지 본 문자열이

....+-로 끝나면 그 전 문자열의 값에 +1이 된 것으로 해석

....--로 끝나면 그 전 문자열의 값에 -1이 된 것으로 해석

....++로 끝나면 그 전 문자열의 값에 +10이 된 것으로 해석

....-+로 끝나면 그 전 문자열의 값에 -10이 된 것으로 해석

....++-로 끝나면 그 전 문자열의 값에 +11이 된 것으로 해석

....-+-로 끝나면 그 전 문자열의 값에 -11이 된 것으로 해석

가능하다.

그러니까 어떤 식으로 끝나는지를 조사해 나올 수 있는 모든 해석 가능성들 중 가장 큰 값을 dp[i]에 저장하면 된다.

어떤 방법으로도 해석이 불가한 경우는 dp[i]값에 -2000000000(마이너스 20억)을 저장하는 것으로 했다.

 

다음은 C언어로 구현한 것이다.

int main()
{
	char s[200006];
	scanf("%s", s);
	int dp[200006];
	int k = strlen(s);
	dp[0] = s[0] == '+' ? 10 : 1;
	if (s[0] == '+' && s[1] == '-')
		dp[1] = 11;
	else
		dp[1] = -2000000000;
	int a3 = s[0] == '+' ? 10 : 1;
	int b3 = s[2] == '+' ? 10 : 1;
	if (s[1] == '+')
		dp[2] = a3 + b3;
	else
		dp[2] = a3 - b3;

	for (int i = 3;i < k;i++)
	{
		int p = -2000000000;
		if (s[i] == '+')
		{
			if (s[i - 1] == '+')
			{
				if (dp[i - 2] != -200000000)
					p = max(p, dp[i - 2] + 10);
			}
			else
			{
				if (dp[i - 2] != -200000000)
					p = max(p, dp[i - 2] - 10);
			}
		}
		else
		{
			if (s[i - 1] == '+')
			{
				if (dp[i - 2] != -200000000)
					p = max(p, dp[i - 2] + 1);
				if (s[i - 2] == '+')
				{
					if (dp[i - 3] != -200000000)
						p = max(p, dp[i - 3] + 11);
				}
				else
				{
					if (dp[i - 3] != -200000000)
						p = max(p, dp[i - 3] - 11);
				}
			}
			else
			{
				if (dp[i - 2] != -200000000)
					p = max(p, dp[i - 2] - 1);
			}
		}
		dp[i] = p;
	}
	printf("%d", dp[k - 1]);
}