2024-03-12

-합 분해(2225, 백준)

 간단한 Dp문제였다.Dp[i][j] = j개의 수를 사용하여 수 i를 만드는 방법의 수로 정의하고 풀었다.

>점화식<

dp[i][j] = (dp[i][j] + dp[i - l][j - 1])

<소스 코드>

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, k;
long long dp[210][210];

int main()
{
	int i, j;
	scanf("%d %d", &n, &k);
	for (i = 0; i <= n; i++) dp[i][1] = 1;
	for (i = 0; i <= n; i++) {
		for (j = 1; j <= k; j++) {
			for (int l = 0; l <= i; l++) {
				dp[i][j] = (dp[i][j] + dp[i - l][j - 1]) % 1000000000;
			}
		}
	}
	printf("%lld", dp[n][k]);
	return 0;
}

-내려 가기(2096, 백준)

 간단한 Dp문제였다. 점화식을 떠올리는 난이도는 어렵지 않지만, 메모리 제한이 빡빡하기에 입력받으며, 동시에 Dp를 돌려주는 식으로 풀어야한다.최댓값과 최솟값에 해당하는 Dp배열을 각각 구해주었다.

>점화식<

dp_mn[1][k] = min(dp_mn[1][k], dp_mn[0][j] + arr[k]);

dp[1][k] = max(dp[1][k], dp[0][j] + arr[k]);

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <cmath>

using namespace std;

int n;
int arr[4];
int dp[2][4], dp_mn[2][4];

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= 3; j++) {
			dp[0][j] = dp[1][j], dp[1][j] = -2e9;
			dp_mn[0][j] = dp_mn[1][j], dp_mn[1][j] = 2e9;
		}
		for (j = 1; j <= 3; j++) {
			scanf("%d", &arr[j]);
		}
		for (j = 1; j <= 3; j++) {
			for (int k = 1; k <= 3; k++) {
				if (abs(j - k) > 1) continue;
				dp[1][k] = max(dp[1][k], dp[0][j] + arr[k]);
			}
		}
		for (j = 1; j <= 3; j++) {
			for (int k = 1; k <= 3; k++) {
				if (abs(j - k) > 1) continue;
				dp_mn[1][k] = min(dp_mn[1][k], dp_mn[0][j] + arr[k]);
			}
		}
	}
	int ans_mx = max(dp[1][1], max(dp[1][2], dp[1][3]));
	int ans_mn = min(dp_mn[1][1], min(dp_mn[1][2], dp_mn[1][3]));
	printf("%d %d", ans_mx, ans_mn);
	return 0;
}

-공통 부분 문자열(5582, 백준)

 보자마자 LCS가 생각났다. LCS와는 다르게 연속된 문자열이여야 함으로, 두 문자가 서로 같을 때만 DP를 채우면 된다.

>점화식<

if (s1[i] == s2[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);

<소스 코드>

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

char s1[4010], s2[4010];
int n1, n2;
int dp[4010][4010];
int ans = 0;

int main()
{
	int i, j;
	scanf("%s", s1 + 1);
	scanf("%s", s2 + 1);
	s1[0] = '0', s2[0] = '0';
	n1 = strlen(s1) - 1;
	n2 = strlen(s2) - 1;
	for (i = 1; i <= n1; i++) {
		for (j = 1; j <= n2; j++) {
			if (s1[i] == s2[j]) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
				if (dp[i][j] > ans) ans = dp[i][j];
			}
		}
	}
	printf("%d", ans);
	return 0;
}

-Dance Dance Revolution (2342, 백준)

 간단한 2차원 Dp문제였다.Dp[i][L][R] = i번째 지시에 왼쪽발이 L에 오른쪽발이 R에 있는 경우로 두고 풀었다. 자세히 분석하기 귀찮아서 모든 경우를 직접 구해 구현했다. O(N*5*5)라 시간초과는 안났다.

<소스 코드>

#include <stdio.h>
#include <algorithm>

using namespace std;

int dp[100010][5][5];

int main()
{
	int i, j;
	for (i = 0; i <= 100000; i++) {
		for (j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				dp[i][j][k] = 2e9;
			}
		}
	}
	dp[0][0][0] = 0;
	i = 0;
	while (1)
	{
		int x;
		i++;
		scanf("%d", &x);
		if (x == 0) break;
		for (j = 0; j <= 4; j++) {
			for (int k = 0; k <= 4; k++) {
				if (k == x) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 1);
				if (j == x) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 1);
				if (k == 0) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 2);
				if (j == 0) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 2);
				if (k == 1) {
					if (x == 2) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 3);
					else if (x == 4) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 3);
					else if (x == 3) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 4);
				}
				if (j == 1) {
					if (x == 2) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 3);
					else if (x == 4) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 3);
					else if (x == 3) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 4);
				}

				if (k == 2) {
					if (x == 1) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 3);
					else if (x == 4) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 4);
					else if (x == 3) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 3);
				}
				if (j == 2) {
					if (x == 1) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 3);
					else if (x == 4) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 4);
					else if (x == 3) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 3);
				}

				if (k == 3) {
					if (x == 2) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 3);
					else if (x == 4) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 3);
					else if (x == 1) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 4);
				}
				if (j == 3) {
					if (x == 2) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 3);
					else if (x == 4) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 3);
					else if (x == 1) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 4);
				}

				if (k == 4) {
					if (x == 2) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 4);
					else if (x == 1) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 3);
					else if (x == 3) dp[i][j][x] = min(dp[i][j][x], dp[i - 1][j][k] + 3);
				}
				if (j == 4) {
					if (x == 2) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 4);
					else if (x == 1) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 3);
					else if (x == 3) dp[i][x][k] = min(dp[i][x][k], dp[i - 1][j][k] + 3);
				}
			}
		}
	}
	int ans = 2e9;
	for (j = 0; j <= 4; j++) {
		for (int k = 0; k <= 4; k++) {
			ans = min(ans, dp[i - 1][j][k]);
		}
	}
	printf("%d", ans);
	return 0;
}

소스가 너무 비효율적인것같긴 하다.