KOI 2018 초등부 문제 풀이

한국정보올림피아드 (KOI) 2018년도 초등부 문제 풀이입니다.

https://www.acmicpc.net/category/detail/1894

KOI 2018 초등부

 

백준저지에서 문제를 확인 / 풀이가 가능합니다.

 

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

15969번: 행복

1번 행복 (백준 15969)

1번 행복 문제입니다.

 

아주 간단한 문제이죠. 최대값과 최소값을 구해서 뺀 뒤 출력하면 됩니다.

 

파이썬2으로 풀어보았습니다.

 

input();a=map(int,raw_input().split());print max(a)-min(a)

 

 

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

15970번: 화살표 그리기

2번 화살표 그리기 (백준 15970)

2번 화살표 그리기 문제입니다.

 

그리디하게 가장 가까운 녀석들에 화살표를 잇고 그 길이를 모두 더하면 되는 문제입니다.

색상이 흑과 백, 2가지만 나오지 않고 N가지가 나온다는 점에 유의 하여

 

색깔별로 다른 vector에 저장한 뒤, 정렬하여 인접한 녀석 중 가까운 곳에 잇는 방식으로 풀 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
vector<int> A[5005];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int pos, col;
		cin >> pos >> col;
		A[col-1].push_back(pos);
	}
	for (int i = 0; i < N; i++) {
		sort(A[i].begin(), A[i].end());
	}
	int ans = 0;
	for (int j = 0; j < N; j++) {
		for (int i = 0; i < A[j].size(); i++) {
			int prev, next;
			prev = next = 987654321;
			if (i > 0) {
				prev = A[j][i] - A[j][i - 1];
			}
			if (i + 1 < A[j].size()) {
				next = A[j][i + 1] - A[j][i];
			}
			ans += min(prev, next);
		}
	}
	cout << ans << endl;
	return 0;
}

 

 

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

15971번: 두 로봇

3번 두 로봇 (백준 15971)

3번 두 로봇 문제입니다.

 

그림만 봐도 Graph 문제인 것을 알 수 있겠죠?

 

총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 방, …, N번 방으로 부른다. 통로는 정확히 N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜 주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는 것이 가능하며, 임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다.

 

이 조건을 보아서, 이 Graph는 트리입니다.

 

서로 다른곳에 있는 로봇이 만나기 위해 이동해야 하는 거리의 최소값을 구해야 합니다. 두 점의 최단거리 문제이죠.

 

그리고 한 Edge에 대해서는 이동하지 않고 통신을 할 수 있기 때문에, 그냥 최단거리 문제는 아닙니다.

 

Edge의 Weight값이 균일하지 않기 때문에 Dijkstra Shortest Path 알고리즘으로 풀 수 있으며, 한 Edge의 값은 제거할 수 있기 때문에 지난 Edge 중 가장 큰 Edge weight 값을 가지고 있다가, 총 거리에서 해당 Largest Edge weight를 제거하면 정답이 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 100005
vector<pii> edges[MAXN];
bool visit[MAXN];

struct State {
	int pos, totallen, maxseg;
	bool operator<(const State& rhs) const {
		return totallen > rhs.totallen;
	}
};
int main() {
	int N, A, B;
	cin >> N >> A >> B;
	for (int i = 1; i < N; i++) {
		int src, dst, len;
		cin >> src >> dst >> len;
		edges[src].push_back(make_pair(dst, len));
		edges[dst].push_back(make_pair(src, len));
	}
	priority_queue<State> pq;
	pq.push({ A, 0, 0 });
	while (pq.size()) {
		State state = pq.top(); pq.pop();
		int pos = state.pos;
		visit[pos] = true;
		if (pos == B) {
			cout << (state.totallen - state.maxseg) << endl;
            return 0;
		}
		for (auto next : edges[pos]) {
			int next_pos = next.first;
			int next_seglen = next.second;
			if (visit[next_pos] == false) {
				pq.push({ next.first, state.totallen + next_seglen, max(state.maxseg, next_seglen) });
			}
		}
	}

}

 

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

15972번: 물탱크

4번 물탱크 (백준 15972)

4번 물탱크 문제입니다.

 

아이디어를 생각해내기 좀 어려웠는데요, 풀고 나서도 왜 이게 풀렸는지 지금 100% 이해가 된 상태는 아닙니다.

 

일단 Graph 문제로 환원하여 생각을 하였고, 외부와 직/간접적으로 연결된 녀석들은 물이 셀 수 있습니다.

 

직접적으로 연결된 녀석은 그 연결된 구멍의 높이만큼 물이 세어나가게 되고, 간접적으로 연결된 녀석은 조건에 따라서 물이 세어나갈수도 있고 아닐 수도 있습니다.

 

외부에서 부터 Graph 탐색을 한다고 하였을 때, 간접적으로 외부와 연결된 내부 공간들이 탐색이 되게 되는데, 

 

이때 외부로 연결되는 구멍의 높이가 높아지는 경우와 낮아지는 경우가 있습니다. 

 

외부와 연결되는 구멍의 높이가 높아지는 경우는 최근 구멍의 높이만큼 물이 줄줄 세개 됩니다.

 

 

구멍의 높이가 낮아지는 경우는, 최근 연결된 녀석의 수심만큼만 물이 줄줄 세어나가게 됩니다.

 

이러한 특징을 활용해서 변형된 Dijkstra 최단거리 알고리즘으로 문제를 풀이했습니다.

 

구멍 높이가 낮은 녀석부터 먼저 탐색하도록 하였고, 이게 문제가 풀릴지 아닐지 몰랐는데, 풀리긴 하더군요.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

struct Edge{
	int x, y, h;
};
struct State {
	int x, y, sx, sy, h;
	bool operator<(const struct State& rhs) const {
		return h > rhs.h;
	}
};
vector<Edge> edges[1005][1005];
int height[1005][1005];
bool visit[1005][1005];

int main() {
	int N, M, H;
	scanf("%d%d%d", &N, &M, &H);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			height[i][j] = H;
		}
	}

	for (int i = 0; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			/*
			(i,j) ~ (i+1, j)
			*/
			int v;
			scanf("%d", &v);
			if (~v) {
				edges[i][j].push_back({ i + 1, j, v });
				edges[i + 1][j].push_back({ i, j, v });
			}
		}
	}
	for (int j = 1; j <= N; j++) {
		for (int i = 0; i <= M; i++) {
			/*
			(j, i) ~ (j, i+1)
			*/
			int v;
			scanf("%d", &v);
			if (~v) {
				edges[j][i].push_back({ j, i + 1, v });
				edges[j][i + 1].push_back({ j, i, v });
			}
		}
	}
	priority_queue<State> pq;
	for (int i = 0; i <= M + 1; i++) {
		int x = 0;
		int y = i;
		visit[x][y] = true;
		for (auto next : edges[x][y]) {
			pq.push({ next.x, next.y, x, y, next.h });
		}
	}
	for (int i = 0; i <= M + 1; i++) {
		int x = N + 1;
		int y = i;
		visit[x][y] = true;
		for (auto next : edges[x][y]) {
			pq.push({ next.x, next.y, x, y, next.h });
		}
	}

	for (int i = 1; i <= N; i++) {
		int x = i;
		int y = 0;
		visit[x][y] = true;
		for (auto next : edges[x][y]) {
			pq.push({ next.x, next.y, x, y, next.h });
		}
	}
	for (int i = 1; i <= N; i++) {
		int x = i;
		int y = M + 1;
		visit[x][y] = true;
		for (auto next : edges[x][y]) {
			pq.push({ next.x, next.y, x, y, next.h });
		}
	}

	while (pq.size()) {
		auto state = pq.top(); pq.pop();
		int x = state.x;
		int y = state.y;
		int sx = state.sx;
		int sy = state.sy;
		int h = state.h;
		if (visit[x][y] == false) {
			visit[x][y] = true;
			height[x][y] = min(height[x][y], max(h, height[sx][sy]));
			for (auto eg : edges[x][y]) {
				if (visit[eg.x][eg.y] == false) {
					pq.push({ eg.x, eg.y, x, y, eg.h });
				}
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			ans += height[i][j];
		}
	}
	printf("%d\n", ans);

	return 0;
}