굳건하게

문제 : https://www.acmicpc.net/problem/15988

[ 알고리즘풀이 ]

DP[N] : N을 1, 2, 3으로 만드는 경우의 수.

DP[N] = DP[N - 1] + DP[N - 2] + DP[N - 3] 성립.

#include<iostream>
#define M 1000000009

using namespace std;

int N, K, dp[1000001] = { };


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 4;
	for (int i = 4; i <= 1000000; i++)
		dp[i] = ((dp[i - 1] + dp[i - 2]) % M + dp[i - 3]) % M;

	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		cout << dp[n] << '\n';
	}
	return 0;
}

문제 : https://www.acmicpc.net/problem/12101

[ 알고리즘풀이 ]

1. DP[X] : X를 1, 2, 3을 이용해서 표현할 수 있는 경우의 수.

→ DP[X] = DP[X - 1] + DP[X - 2] + DP[X - 3]

2. N, K 가 입력되면 DP[N] 값과 K를 비교해 나올 수 없는 경우 -1을 출력하고,

아니라면 K를 DP[N - 1], DP[N - 2], DP[N - 3] 과 비교해서 1, 2, 3 중 해당되는 값을 재귀적으로 출력한다.

#include<iostream>

using namespace std;

int N, K, dp[11] = { };

void printAnswer(int N, int K) {
	if (dp[N] < K){
		cout << -1;
		return;
	}
	for (int i = 1; ; i++) {
		if (dp[N - i] >= K) {
			if (N - i > 0){
				cout << i << '+';
				printAnswer(N - i, K);
			}
			else
				cout << i;
			break;
		}
		K -= dp[N - i];
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> K;
	
	dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 4;
	for (int i = 4; i < 11; i++)
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

	printAnswer(N, K);
	return 0;
}

문제 : https://www.acmicpc.net/problem/17144

[ 알고리즘풀이 ]

1. 미세먼지 확산

map[x][y] : 현재 (x, y) 지점에 있는 먼지의 양.

dustmap[x][y] : (x,y) 지점에 미세먼지 확산으로 인해 추가될 먼지의 양.

map을 순회하며, 미세먼지가 있다면 주변의 dustmap에 추가될 미세 먼지의 양을 더해줍니다.

순회가 끝났다면, 다시 순회하며 map에 dustmap을 더해주고, dustmap을 0으로 초기화해줍니다.

dustmap을 따로 선언하지않는다면, map에 새롭게 추가되는 먼지와 이미 있던 먼지를 구분할 수 없으므로 map, dustmap 2개의 배열을 이용하면 됩니다.

2. 공기청정기 작동

기존에 공기 청적이의 위치를 따로 저장해 두고, 공기청정기 상단, 하단을 각각 작동시켜 한 칸씩 배열을 shift 하면 됩니다.

#include<iostream>
#include<queue>

using namespace std;

int R, C, T, dustmap[50][50] = {}, map[50][50] = {}, dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
int firstR, secondR;
int curDust(void) {
	int sum = 0;
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			if (map[i][j] != -1)
				sum += map[i][j];
	return sum;
}

void spreadDust(void) {
	for(int i = 0; i < R; i++)
		for (int j = 0; j < C; j++) {
			if (map[i][j] != -1 && map[i][j] != 0) {
				int dust = map[i][j] / 5;
				for (int k = 0; k < 4; k++) {
					int nextX = i + dx[k], nextY = j + dy[k];
					if (nextX < 0 || R <= nextX || nextY < 0 || C <= nextY)
						continue;
					if (map[nextX][nextY] == -1)
						continue;
					dustmap[nextX][nextY] += dust;
					map[i][j] -= dust;
				}
			}
		}
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++){
			if (map[i][j] != -1)
				map[i][j] += dustmap[i][j];
			dustmap[i][j] = 0;
		}
	return;
}

void clearAir(void) {
	// 위쪽순환
	for (int i = firstR - 1; i > 0; i--)
		map[i][0] = map[i - 1][0];
	for (int j = 0; j < C - 1; j++)
		map[0][j] = map[0][j + 1];
	for (int i = 0; i < firstR; i++)
		map[i][C - 1] = map[i + 1][C - 1];
	for (int j = C - 1; j > 1; j--)
		map[firstR][j] = map[firstR][j - 1];
	map[firstR][1] = 0;
	// 아래쪽순환
	for (int i = secondR + 1; i < R - 1; i++)
		map[i][0] = map[i + 1][0];
	for (int j = 0; j < C - 1; j++)
		map[R - 1][j] = map[R - 1][j + 1];
	for (int i = R - 1; i > secondR; i--)
		map[i][C - 1] = map[i - 1][C - 1];
	for (int j = C - 1; j > 1; j--)
		map[secondR][j] = map[secondR][j - 1];
	map[secondR][1] = 0;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> R >> C >> T;
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++){
			cin >> map[i][j];
		}
	// 공기청정기 위치 확인
	for (int i = 0; i < R; i++)
		for(int j = 0; j < C; j++)
			if (map[i][j] == -1) {
				firstR = i, secondR = i + 1;
				i = R, j = C;
			}

	while (T--) {
		spreadDust();
		clearAir();
	}
	cout << curDust();
	return 0;
}

문제 : https://www.acmicpc.net/problem/1261

[ 알고리즘풀이 ]

1. BFS 탐색을 진행한다.

2. visit 배열을 dp배열로 선언한다.

dp[x][y] : (0, 0)에서 (x, y) 지점까지 오는데 필요한 벽을 부수는 최소 횟수.

현재 지점에서 다음 지점으로 넘어갈 때, 벽이라면 현재 dp 값 + 1 보다 크면 탐색을 진행하고,

벽이 아니라면 현재 dp값 보다 크면 탐색을 진행한다.

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, m, dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 }, dp[100][100] = {};
	char map[100][101] = {};

	cin >> m >> n;
	for (int i = 0; i < n; i++)
		cin >> map[i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			dp[i][j] = 99999999;

	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	dp[0][0] = 0;

	while (!q.empty()) {
		pair<int, int> s = q.front();
		q.pop();

		int curX = s.first, curY = s.second;
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i], nextY = curY + dy[i];
			if (0 <= nextX && nextX < n && 0 <= nextY && nextY < m) {
				if (dp[curX][curY] + 1 < dp[nextX][nextY] && map[nextX][nextY] == '1') {
					dp[nextX][nextY] = dp[curX][curY] + 1;
					q.push(make_pair(nextX, nextY));
				}
				else if(dp[curX][curY] < dp[nextX][nextY] && map[nextX][nextY] == '0'){
					dp[nextX][nextY] = dp[curX][curY];
					q.push(make_pair(nextX, nextY));
				}
			}
		}
	}
	cout << dp[n - 1][m - 1];
	return 0;
}