[BOJ] 백준 14867. 물통 (Gold II)

스터디그룹에서 연습 C번으로 진행된 문제.

어떻게 보면 되게 쉽지만, 어떻게 보면 마냥 쉽지만은 않은 문제.

문제는 아래와 같다.

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

14867번: 물통

---

의식의 흐름 및 해설

물통 물 양이 각각 C, D가 되기 위한 최소 횟수를 구하는 문제.

이런 유형은 보통 BFS로 접근하는데, 문제는 N이 최대 10만이라 이차원배열로 방문체크를 하면 무조건 시간초과 혹은 메모리초과가 난다.

여기서 BFS 접근을 버리고 다른 풀이를 생각하려 한다면 조금 힘들어질 것이다... 물론 수학/조합론 쪽으로 생각한다면 구제 가능성은 있지만..

 

이 문제는 잘 생각해보면 시간복잡도가 O(CD)가 아니다.

문제에서 A<B이므로 일단 B만큼 한쪽 물통을 다 채운다고 해보자.

그리고 이 경우에서 두 물통 양의 합이 B가 될 수 있는 경우를 모두 구해보자.

(0, B), (A, B-A).

오잉? 끝이다. (A, B-2A), (A, B-3A)와 같이 B의 물통의 양을 계속 A로 넘겨줄 수도 있지만, 이 때는 두 물통의 양의 합이 B보다 적어진다.

 

따라서 경우의 수는 O(CD)가 아니라 O(k*(C+D)) (k=2) 에 불과하다.

음... k=3까지도 가능하려나... 확실한건 무조건 O(CD)보단 훨~씬 적다.

 

따라서 bool[MAXN][MAXN]이 아닌 set으로 중복체크를 해주자.

map으로 해줘도 되지만 set이 더 빠르니까 set으로 해주자.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
const int MAX = 100011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int a, b, c, d;
set<pi> s;
int bfs() {
	queue<pii> q;
	q.push({ 0,{0,0} });
	s.insert({0,0});
	while (!q.empty()) {
		int x = q.front().second.first;
		int y = q.front().second.second;
		int time = q.front().first;
		q.pop();
		if (x == c && y == d) {
			return time;
		}
		if (x<a && !s.count( {a,y} )) {
			s.insert({ {a,y} });
			q.push({ time + 1,{a,y} });
		}
		if (y<b&&!s.count({x,b})) {
			s.insert({ x,b });
			q.push({ time + 1,{x,b} });
		}
		if (x && !s.count({0,y})) {
			s.insert({0,y});
			q.push({ time + 1,{0,y} });
		}
		if (y&&!s.count({x,0})) {
			s.insert({ x,0 });
			q.push({ time + 1,{x,0} });
		}
		int k = min(x, b - y);
		if (x && k && !s.count({x-k, y+k})) {
			s.insert({ x-k, y+k });
			q.push({ time + 1, {x-k,y+k} });
		}
		k = min(y, a - x);
		if (y && k && !s.count({x+k, y-k})) {
			s.insert({ x + k, y - k });
			q.push({ time + 1, {x + k, y - k} });
		}
	}
	return -1;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> a >> b >> c >> d;
	cout << bfs();
}

---

찍맞으로 맞추는 경우가 너무 많아서 G4~G5로 내려갈 것 같은 문제.

이래서 알고리즘 분류를 보면 안된다고 생각한다.

대회 때는 어떤 알고리즘을 써야 하는지 알려주지 않기 때문에 스스로 고민하면서 삽질도 해보면서 실력을 늘려야 한다고 생각한다.

(근데 이게 쉽지가 않다... 넘 답답하면 알고리즘 분류가 '나를 클릭해~~'라고 달콤하게 유혹해버리긴 하지만, 그걸 떨쳐내도록 하자 ㅎㅎ)