취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15806번 문제인 영우의 기숙사 청소이다.
문제는 아래 링크를 확인하자.

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

일반적으로, 현재 단계에 피어있는 곰팡이는 다다음 단계에 그 위치에 그대로 다시 피어나게 된다는 점을 관찰하자. 해당 곰팡이가 퍼뜨린 포자가 다음 단계에 다시 원위치에도 포자를 퍼뜨리기 때문이다.

위의 관찰을 이용해, 짝수단계와 홀수단계에 퍼져있는 곰팡이의 모습을 각각 bfs를 통해 퍼뜨리는 것으로 문제를 해결할 수 있다.

단, 현재 단계에 피어있는 곰팡이가 포자를 퍼뜨릴 수 없는 경우는 예외이다. 초기 상태에서만 그러한 경우를 찾을 수 있는데, 그 외의 경우 이전 단계에서 해당 위치로 곰팡이 포자가 퍼져왔을 수밖에 없기 때문이다. 이에 대한 예외처리를 적절히 생각하고 구현해 문제를 해결하자.

아래는 제출한 소스코드이다.

#define MP(x,y) make_pair(x,y)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M, K, T;
queue<pair<int, int>> que;
bool odd[301][301];
bool even[301][301];

int dr[8] = { 1,2,2,1,-1,-2,-2,-1 };
int dc[8] = { 2,1,-1,-2,-2,-1,1,2 };

void oddbfs() {
	int rep = que.size();
	while (rep--) {
		auto& p = que.front();
		int r = p.first, c = p.second;
		que.pop();
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr<1 || rr>N || cc<1 || cc>N) continue;
			if (odd[rr][cc]) continue;
			odd[rr][cc] = 1;
			que.push(MP(rr, cc));
		}
	}
}

void evenbfs() {
	int rep = que.size();
	while (rep--) {
		auto& p = que.front();
		int r = p.first, c = p.second;
		que.pop();
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr<1 || rr>N || cc<1 || cc>N) continue;
			if (even[rr][cc]) continue;
			even[rr][cc] = 1;
			que.push(MP(rr, cc));
		}
	}
}

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

	cin >> N >> M >> K >> T;;
	while (M--) {
		int r, c; cin >> r >> c;
		que.push(MP(r, c));
	}
	for (int t = 1; t <= T; t++) {
		if (t & 1) oddbfs();
		else evenbfs();
	}

	bool ans = 1;
	while (K--) {
		int r, c; cin >> r >> c;
		if (T & 1) {
			if (odd[r][c]) ans = 0;
		}
		else {
			if (even[r][c]) ans = 0;
		}
	}

	if (ans) cout << "NO";
	else cout << "YES";
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15805번 문제인 트리 나라 관광 가이드이다.
문제는 아래 링크를 확인하자.

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

지문의 첫 문단 서술이 애매해 보충설명하면, 윤호가 구성한 패키지의 도시 방문 순서는 "트리의 모든 도시를 방문하는 가장 짧은" 이동경로임이 보장된다. 즉, 주어지는 경로는 처음 주어지는 노드를 루트로 갖는 모양의 트리에서의 dfs 방문 순서와 같게 된다.

dfs 과정에서 언제 탐색을 퇴각(backtrack)하는지를 생각하며 잘 구현해보자. 스택을 이용하면 편하게 구현할 수 있다.

이러한 이동 과정에서 트리의 모든 에지는 양 방향으로 한 번씩 이용해야하므로, 전체 노드의 개수는 dfs 경로의 길이를 이용해 계산해낼 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> stk;
int ans[100001];

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

	stk.emplace_back(-1);
	stk.emplace_back(-1);
	int idx = 0;

	int N; cin >> N;
	int NN = (N + 1) / 2;

	N--;
	int x; cin >> x;
	ans[x] = -1;
	stk.emplace_back(x);
	idx++;
	
	while (N--) {
		cin >> x;
		if (x == stk[idx]) {
			ans[stk.back()] = stk[idx];
			stk.pop_back();
			idx--;
		}
		else {
			stk.emplace_back(x);
			idx++;
		}
	}

	cout << NN << '\n';
	for (int i = 0; i < NN; i++) cout << ans[i] << ' ';
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15808번 문제인 주말 여행 계획이다.
문제는 아래 링크를 확인하자.

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

(출발지점 가중치) - (두 노드 사이 거리) + (도착지점 가중치)를 최대화하는 문제이다.

-(출발지점 가중치) + (두 노드 사이 거리)를 최소화한 값을 multi source일 때의 최단거리 알고리즘을 이용하여 값을 구한 다음, 각 도착지점에서 위 값을 이용하여 최댓값 후보들을 구하는 것으로 문제를 해결하자.

처음에는 계산실수로 floyd-warshall 알고리즘으로도 통과될 거라고 예상하고 풀이를 시도했으나 시간초과를 받았다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, P, Q;
vector<pair<int, int>> G[1001];

int dist[1001];
bool visited[1001];
priority_queue<pair<int, int>> pq;

void dijkstra() {
	while (!pq.empty()) {
		auto& p = pq.top();
		int cur = p.second, d = -p.first;
		pq.pop();
		if (d > dist[cur]) continue;

		for (auto& pp : G[cur]) {
			int node = pp.first, w = pp.second;
			if (visited[node] == 0) {
				dist[node] = d + w;
				visited[node] = 1;
				pq.push(make_pair(-(d + w), node));
			}
			else if (dist[node] > d + w) {
				dist[node] = d + w;
				pq.push(make_pair(-(d + w), node));
			}
		}
	}
}

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

	cin >> N;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			int x; cin >> x;
			if (x) G[r].emplace_back(make_pair(c, x));
		}
	}

	cin >> P >> Q;
	while (P--) {
		int x, w; cin >> x >> w;
		visited[x] = 1;
		dist[x] = -w;
		pq.push(make_pair(w, x));
	}

	dijkstra();

	int ans = -1000000007;
	while (Q--) {
		int x, w; cin >> x >> w;
		ans = max(ans, -dist[x] + w);
	}

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15804번 문제인 저거 못 타면 지각이야!!이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어지는 버스정류장은 큐의 형태로 모델링이 가능하다.

문제 조건에서 주어진 순서를 이용해 각 버스가 들어올 때마다 (1) 나갈 수 있는 버스를 모두 내보내고, (2) 해당 버스가 들어올 빈 자리가 있으면 들여보내고 (3) 자리가 없다면 모든 버스를 내보낼 때까지 기다린 뒤 해당 버스를 정류장에 집어넣는 시뮬레이션을 돌려 문제를 해결하자.

위 시뮬레이션을 돌릴 때, 새로 들어오는 버스의 도착시간은 항상 이전에 들어오는 버스의 도착시간 이상이 되어야 한다는 점을 확인하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <deque>
using namespace std;

struct bus {
	int arrive;
	int depart;
	int idx;
	bus(int arrive, int depart, int idx) {
		this->arrive = arrive, this->depart = depart, this->idx = idx;
	}
};

int N, M;
deque<bus> dq;

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

	cin >> N >> M;
	while (M--) {
		int arrive, depart; cin >> arrive >> depart;
		while (!dq.empty()) {
			if (dq.front().depart <= arrive) dq.pop_front();
			else break;
		}

		if (dq.empty()) dq.push_back(bus(arrive, arrive + depart, 1));
		else if (dq.back().idx == N) {
			while (!dq.empty()) {
				arrive = max(arrive, dq.front().depart);
				dq.pop_front();
			}
			dq.push_back(bus(arrive, arrive + depart, 1));
		}
		else {
			arrive = max(arrive, dq.back().arrive);
			dq.push_back(bus(arrive, arrive + depart, dq.back().idx + 1));
		}
	}
	cout << dq.back().idx;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15803번 문제인 PLAYERJINAH’S BOTTLEGROUNDS이다.
문제는 아래 링크를 확인하자.

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

서로 다른 세 점이 주어질 때, 이 세 점이 한 직선 위에 있는지를 판정하는 문제이다.

사선공식(shoelace formula)를 이용해 세 점이 이루는 삼각형의 넓이를 구하면 세 점이 한 직선 위에 있을 경우 0, 아닌 경우 0이 아닌 값이 나온다는 점을 이용하면 세 점이 직선 위에 있는지를 판정할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

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

	int x1, y1, x2, y2, x3, y3; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
	if (x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x3 * y2 - x2 * y1 == 0) cout << "WHERE IS MY CHICKEN?";
	else cout << "WINNER WINNER CHICKEN DINNER!";
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15807번 문제인 *빛*영*우*이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어지는 모든 좌표는 3001*3001의 2차원 배열로 나타낼 수 있다는 점을 이용하자.

2차원 imos법을 응용하면 입력으로 들어올 수 있는 모든 범위의 빛의 강도를 미리 전처리할 수 있다. 이 때, 입력 좌표는 3001*3001의 배열로 나타나지만 imos법으로 표기해야하는 범위는 그보다 넓게 잡아야 할 수 있다는 점에 유의하자.

imos법 대신 세그먼트트리를 이용한 다른 풀이 또한 존재한다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, P;
int arr[3002][6004];

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

	cin >> N;
	while (N--) {
		int r, c; cin >> c >> r;
		r += 1500, c += 1500;
		arr[r][c]++, arr[r + 1][c]++;
	}
	
	for (int c = 3000; c > 0; c--) {
		int rr = 0, cc = c;
		while (rr < 3000) {
			arr[rr + 1][cc + 1] += arr[rr][cc];
			rr++, cc++;
		}
	}
	for (int r = 0; r < 3000; r++) {
		int rr = r, cc = 0;
		while (rr < 3000) {
			arr[rr + 1][cc + 1] += arr[rr][cc];
			rr++, cc++;
		}
	}
	for (int c = 0; c < 6004; c++) {
		int rr = 0, cc = c;
		while (rr < 3000) {
			arr[rr + 1][cc - 1] += arr[rr][cc];
			rr++, cc--;
		}
	}

	cin >> P;
	while (P--) {
		int r, c; cin >> c >> r;
		r += 1500, c += 1500;
		cout << arr[r][c] << '\n';
	}
}