[BAEKJOON] 13398, 18405, 21610

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[gold5, 11398 연속합2] - 다이나믹 프로그래밍(DP)

수를 제거하지 않은 경우와 제거한 경우를 각각 sum[i][0], sum[i][1]배열에 저장한다 할 때
 
수를 제거하지 않는 경우엔 연속된 구간의 합이 수열의 다음 수보다 작은 경우, 수열의 다음수 부터 새로운 구간을 시작하게 된다
이를 통해 연속합을 저장하는 sum[i][0]배열의 값은 max(sum[i - 1][0] + num[i], num[i])라는 점화식을 끌어낼 수 있다
 
현재를 기준으로 수를 제거한 경우를 생각해보면
1) 현재를 제거하는 경우: sum[i - 1][0]
2) 이미 제거된 경우: sum[i - 1][1] + num[i]
이와 같은 두 식이 나오게되고, 이중 큰 값을 수를 제거한 경우인 sum[i][1]배열 값에 넣는다
 
과정이 진행될 때, 현재를 기준으로 sum[i][0]과 sum[i][1]중 큰 값을, 연속된 구간의 수열 중 가장 큰 값과 비교하며 넘어간다

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

int N, answer;
int num[100001];
int sum[100001][2];
int main() {
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++) {
		scanf("%d", &num[i]);
	}
	sum[0][0] = num[0];
	sum[0][1] = num[0];
	answer = num[0];
	for (int i = 1; i < N; i++) {
		sum[i][0] = max(sum[i - 1][0] + num[i], num[i]);
		sum[i][1] = max(sum[i - 1][0], sum[i - 1][1] + num[i]);
		answer = max(answer, max(sum[i][0], sum[i][1]));
	}
	printf("%d", answer);
}

 

[gold5, 18405 경쟁적 전염] - 너비우선탐색(BFS)

바이러스는 1~K까지 순서대로 증식함을 확인하고, 결과값이 (X=행, Y=행), 1<=X, Y 임에 주의하라
또한, N개의 바이러스가 모두 증식한 뒤가 1초임에 유의하라
 
priority_queue를 사용할 때, 가장 중요한 것은 Compare을 구현하는 것이다
struct로 선언하여 bool operator()(int a, int b){}를 overriding 해야함을 잊지말자

#include <iostream>
#include <queue>
#include <vector>
#pragma warning(disable:4996)

using namespace std;

int N, K, S, Y, X;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int map[201][201];
struct Data {
	int y, x, v;
};
struct dataCompare {
	bool operator()(Data a, Data b) {
		return a.v > b.v;
	}
};
priority_queue <Data, vector<Data>, dataCompare> pq;
bool range(int y, int x) {
	return y<0 || x<0 || y>N - 1 || x>N - 1;
}
int main() {
	scanf("%d %d", &N, &K);
	for(int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j]) pq.push({ i, j, map[i][j] });
		}
	scanf("%d %d %d", &S, &X, &Y);

	int cnt = 0;
	while (!pq.empty()) {
		if (cnt == S) break;
		int pqSize = pq.size();
		cnt++;
		priority_queue <Data, vector<Data>, dataCompare> next_pq;
		for (int i = 0; i < pqSize; i++) {
			Data prev = pq.top(); pq.pop();
			for (int d = 0; d < 4; d++) {
				int ny = prev.y + dy[d];
				int nx = prev.x + dx[d];
				int nv = prev.v;
				if (!range(ny, nx) && !map[ny][nx]) {
					map[ny][nx] = nv;
					next_pq.push({ ny, nx, nv });
				}
			}
		}
		pq = next_pq;
	}
	printf("%d", map[X - 1][Y - 1]);
}

 

[gold5, 21610 마법사 상어와 비바라기] - 구현 + 시뮬레이션

주어진 조건에 따라 차분히 구현하면 쉽게 풀어나갈 수 있는 문제다

단, 구름이 움직일 때 배열을 순회하므로 모듈러 연산을 활용하여 N이하의 최소 움직임을 찾고

1) 좌표가 0보다 작다면 N + (좌표), 2) 좌표가 0보다 크다면, (좌표) - N 

#include <iostream>
#include <string.h>
#include <vector>
#pragma warning(disable:4996)

using namespace std;

int N, M;
int dy[] = { 0,-1,-1,-1,0,1,1,1 };
int dx[] = { -1,-1,0,1,1,1,0,-1 };
int cy[] = { -1,1,1,-1 };
int cx[] = { -1,1,-1,1 };

int basket[101][101];

struct Data {
	int y, x;
};
vector <Data> cloud;
bool visit[101][101];

bool range(int y, int x) {
	return y<0 || x<0 || y>N - 1 || x>N - 1;
}
void initCloud() {
	cloud.push_back({ N - 1, 0 });
	cloud.push_back({ N - 1, 1 });
	cloud.push_back({ N - 2, 0 });
	cloud.push_back({ N - 2, 1 });
}
void moveCloud(int d, int s) {
	int len = cloud.size();
	for (int i = 0; i < len; i++) {
		int ny = cloud[i].y + (dy[d] * s) % N;
		int nx = cloud[i].x + (dx[d] * s) % N;
		if (ny < 0) ny = N + ny;
		else if (ny >= N) ny = ny - N;
		if (nx < 0) nx = N + nx;
		else if (nx >= N) nx = nx - N;
		cloud[i] = { ny, nx };
	}	
}
void rainCloud() {
	int len = cloud.size();
	for (int i = 0; i < len; i++) {
		basket[cloud[i].y][cloud[i].x]++;
	}
}
void waterCopyBug() {
	int len = cloud.size();
	for (int i = 0; i < len; i++) {
		int cnt = 0;
		for (int c = 0; c < 4; c++) {
			int ny = cloud[i].y + cy[c];
			int nx = cloud[i].x + cx[c];
			if (!range(ny, nx) && basket[ny][nx]) {
				cnt++;
			}
		}
		basket[cloud[i].y][cloud[i].x] += cnt;
		visit[cloud[i].y][cloud[i].x] = true;
	}
	cloud.clear();
}
void makeCloud() {
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			if (!visit[i][j] && basket[i][j] >= 2) {
				basket[i][j] -= 2;
				cloud.push_back({ i, j });
			}
	memset(visit, 0, sizeof visit);
}
int sumBasketWater() {
	int cnt = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cnt += basket[i][j];
	return cnt;
}
void viewBasket() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%d ", basket[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &basket[i][j]);
		}
	}
	initCloud();
	for (int m = 0; m < M; m++) {
		int d, s;
		scanf("%d %d", &d, &s);
		moveCloud(d - 1, s);
		rainCloud();
		waterCopyBug();
		makeCloud();
		viewBasket();			
	}
	printf("%d", sumBasketWater());
}