2024-03-01

-피보나치 수의 확장(1788, 백준)

 간단한 DP문제였다. 피보나치수를 음수까지 확장시켜 계산하는 문제였는데, 간단히 문제에 나와있는데로 구현하면 맞는다.

>점화식<

양수 : fibo[i] = (fibo[i - 1] + fibo[i - 2])

음수 : fibo[i] = (fibo[i - 2] - fibo[i - 1])

<소스코드>

#include <stdio.h>
#include <math.h>

int n;
long long P_fibo[1000010], M_fibo[1000010];

int main()
{
	int i, j;
	scanf("%d", &n);
	if (n == 0) printf("0\n0");
	else if (n > 0) {
		P_fibo[0] = 0;
		P_fibo[1] = 1;
		for (i = 2; i <= n; i++) P_fibo[i] = (P_fibo[i - 1] + P_fibo[i - 2]) % 1000000000;
		printf("1\n%lld", P_fibo[n]);
	}
	else {
		n *= (-1);
		M_fibo[0] = 0;
		M_fibo[1] = 1;
		for (i = 2; i <= n; i++) M_fibo[i] = (M_fibo[i - 2] - M_fibo[i - 1]) % 1000000000;
		if (M_fibo[n] < 0) printf("-1\n%lld", (-1) * M_fibo[n]);
		else printf("1\n%lld", M_fibo[n]);
	}
	return 0;
}

-스티커(9465, 백준)

 간단한 2차원 DP문제였다. RGB수라는 문제랑 비슷한 느낌을 받았다. DP[i][j] =  i번째줄에 스티커중 j번째(위, 아래)스티커를 땐 경우 구할 수 있는 최대값으로 정의하고 생각해보면 생각보다 쉽게 풀린다.

>점화식<

dp[i][0] = max(dp[i-1][1] + arr[i][0], dp[i-2][1] + arr[i][0]);
dp[i][1] = max(dp[i-1][0] + arr[i][1], dp[i-2][0] + arr[i][1]);

<소스코드>

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

using namespace std;

int arr[100010][3], dp[100010][3];

int main()
{
    int i, j;
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        for(i=0;i<n;i++) scanf("%d", &arr[i][0]);
        for(i=0;i<n;i++) scanf("%d", &arr[i][1]);
        dp[0][0] = arr[0][0];
        dp[0][1] = arr[0][1];
        for(i=1;i<n;i++) {
            dp[i][0] = dp[i-1][1] + arr[i][0];
            dp[i][1] = dp[i-1][0] + arr[i][1];
            if(i >= 2) {
                dp[i][0] = max(dp[i][0], dp[i-2][1] + arr[i][0]);
                dp[i][1] = max(dp[i][1], dp[i-2][0] + arr[i][1]);
            }
        }
        printf("%d\n", max(dp[n-1][0], dp[n-1][1]));
    }
    return 0;
}

 

-삼각 그래프(4883, 백준)

 간단한 DP문제였다. RGB거리랑 굉장히 비슷한 느낌을 받은 문제였다. 가운데에서 시작해 가장 밑의 가운데까지 가는 최소 경로를 구하는 문제이다. Dp[i][j] = i번째 행에 j번째열까지 가는 최소 경로로 정의했다. 정직하게 내려오며, 최소경로를 찾으면 되는 문제이다. (같은 행에서 옆으로 갈때도 처리해야함을 주의하자)

>점화식<

if (k > 0) dp[i][k] = min(dp[i][k], dp[i][k - 1] + arr[i][k]);
if (abs(k - j) <= 1) dp[i][k] = min(dp[i][k], dp[i - 1][j] + arr[i][k]);

<소스코드>

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

using namespace std;

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

int main()
{
	int i, j;
	int t = 1;
	while (1) {
		int x;
		scanf("%d", &x);
		for (i = 0; i < x; i++) {
			for (j = 0; j < 3; j++) {
				dp[i][j] = 2e9;
			}
		}
		if (x == 0) break;
		for (i = 0; i < x; i++) {
			for (j = 0; j < 3; j++) {
				scanf("%d", &arr[i][j]);
			}
		}
		dp[0][1] = arr[0][1];
		dp[0][2] = arr[0][1] + arr[0][2];
		for (i = 1; i < x; i++) {
			for (j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					if (k > 0) dp[i][k] = min(dp[i][k], dp[i][k - 1] + arr[i][k]);
					if (abs(k - j) > 1) continue;
					dp[i][k] = min(dp[i][k], dp[i - 1][j] + arr[i][k]);
				}
			}
		}
		printf("%d. %d\n", t++, dp[x - 1][1]);
/*		for (i = 0; i < x; i++) {
			for (j = 0; j < 3; j++) {
				printf("%d ", dp[i][j]);
			}
			printf("\n");
		}*/
	}
	return 0;
}

-입대(31413, 백준)

 DP문제이다. Dp[i][j] = j번 헌혈을 해서, i일째에 얻을 수 있는 최대 가산점으로 두고 생각해보면, 풀린다. 최대한 헌혈을 적게 해야함으로, Dp테이블을 채운 뒤, 헌혈횟수가 작은 배열부터 올라가며, m을 넘는다면, 해당배열의 헌혈 횟수를 출력하면 된다. 에디토리얼이 올라와있으니, 모르겠으면 보고 풀어보길 추천한다.

>점화식<

dp[i][j] = max(dp[i - 1][j] + arr[i], dp[i - d][j - 1] + a);

<소스코드>

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

using namespace std;
int dp[2010][2010];
int arr[1010];
int n, m, a, d;

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i <= n + d - 1; i++) {
		for (j = 0; j <= n; j++) {
			dp[i][j] = -2e9;
		}
	}
	dp[0][0] = 0;
	for (i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
		dp[i][0] = dp[i - 1][0] + arr[i];
	}
	if (dp[n][0] >= m) {
		printf("0");
		return 0;
	}
	scanf("%d %d", &a, &d);
	for (i = 1; i <= n + d - 1; i++) {
		for (j = 1; j <= n; j++) {
			if (i < d) continue;
			dp[i][j] = max(dp[i - 1][j] + arr[i], dp[i - d][j - 1] + a);
		}
	}
/*	for (i = 0; i <= n + d - 1; i++) {
		for (j = 0; j <= n; j++) {
			if (dp[i][j] == -2e9) printf("INF ");
			else printf("%d ", dp[i][j]);
		}
		printf("\n");
	}*/
	for (i = 0; i <= n; i++) {
		if (dp[n + d - 1][i] >= m) {
			printf("%d", i);
			return 0;
		}
	}
	printf("-1");
	return 0;
}

-미로 탈출(14923, 백준)

벽 부수고 이동하기와 완전히 같은 문제이다. (솔브닥기준 티어는 다름. 왜다르지?)  3차원 거리배열을 잡아준다. (dis[i][j][k] = k번 벽을 부수고 i, j까지 갈때의 최소 거리.) 그 후, BFS를 돌리면 풀린다.

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

int n, m;
int map[1010][1010];
int dis[1010][1010][3];
int dx[5] = { 0, 0, 1, -1 };
int dy[5] = { 1, -1, 0, 0 };

struct dat {
	int x, y, br;
};

void BFS(int x, int y)
{
	int i, j;
	queue <dat> q;
	q.push({ x, y, 0 });
	dis[x][y][0] = 0;
	while (!q.empty()) {
		int n_x = q.front().x, n_y = q.front().y, br = q.front().br;
		q.pop();
		for (i = 0; i < 4; i++) {
			int nx = n_x + dx[i], ny = n_y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (map[nx][ny] == 0 && dis[nx][ny][br] > dis[n_x][n_y][br] + 1) {
				dis[nx][ny][br] = dis[n_x][n_y][br] + 1;
				q.push({ nx, ny, br });
			}
			if (map[nx][ny] == 1 && br == 0 && dis[nx][ny][br + 1] > dis[n_x][n_y][br] + 1) {
				dis[nx][ny][br + 1] = dis[n_x][n_y][br] + 1;
				q.push({ nx, ny, br + 1 });
			}
		}
	}
	return;
}

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	int sx, sy, ex, ey;
	scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
			dis[i][j][0] = 2e9, dis[i][j][1] = 2e9;
		}
	}
	BFS(sx - 1, sy - 1);
	int ans = min(dis[ex - 1][ey - 1][0], dis[ex - 1][ey - 1][1]);
	if (ans == 2e9) printf("-1");
	else printf("%d", ans);
	return 0;
}