[BOJ] 백준 14168. Cow Checklist (Gold I)

우연의 일치로 두번 연속 Farmer John님을 영접하게 됐다.

개인적으로 Farmer John이 나오는 문제를 좋아하는데, 이유는 걍 재밌어서다.

문제는 아래와 같다.

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

14168번: Cow Checklist

문제 요약

Farmer John이 Holstein 1번 소부터 시작해서 Holstein H번 소까지 탐색할건데,

현재 위치에서 다른 소가 위치하는 곳까지 거리가 D라 할 때, Farmer John은 D^2의 에너지를 소요한다.모든 소를 탐색하는데 소요되는 최소 에너지를 구해보자.(참고로 H소, G소를 번갈아서 탐색할 필요는 없다.)

 

주의할 점은 반드시 Holstein 1번 소에서 시작하고, Holstein H번 소에서 종료돼야한다는 것이다.그리고 좀 이상한 점이 있는데 문제 제한에선 H가 1도 된다고 하는데, H가 1이면 말이 안된다. 일단은 좀 이상해서 QNA 게시판에 H가 1인 경우는 따로 질문하긴 했는데, 어떻게 될지 모르겠다.

---

의식의 흐름 및 해설

알고리즘 분류가 dp임을 파악하는데는 그리 오랜 시간이 걸리지 않는다.

똑같은 소를 두 번 방문하는 것만큼 에너지 낭비인 경우는 없으므로 모든 소는 한번씩만 방문하면 되므로 사이클이 생성되지 않는 2차원 dp이다.

 

모든 소를 탐색해야하므로 int curH, int curG가 각각 H-1, G-1에 도달했는지 파악해주면서 이차원dp를 잘 돌리면 된다.

주의할 점은, 소가 두 종류이기 때문에, G[0]은 아직 방문하지 않은 상태임에 주의하자.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#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;
const int MAX = 1011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const ll MOD = 1e9 + 7;
ll H, G, d[MAX][MAX][2];
vector<pl> h, g;
ll dis(pl p1, pl p2) {
	return (p1.first - p2.first) * (p1.first - p2.first)
		+ (p1.second - p2.second) * (p1.second - p2.second);
}
ll dp(int curh, int curg, int flag) {
	if (curh == H - 1 && curg == G - 1)
		return !flag ? 0 : LNF;
	ll& ret = d[curh][curg+1][flag];
	if (ret != -1)
		return ret;
	ret = LNF;
	if (curh < H-1) {
		!flag ? ret = min(ret, dp(curh + 1, curg, 0) + dis(h[curh], h[curh + 1]))
			: ret = min(ret, dp(curh+1, curg, 0) + dis(g[curg], h[curh + 1]));
	}
	if (curg < G-1) {
		!flag ? ret = min(ret, dp(curh, curg+1, 1) + dis(h[curh], g[curg + 1]))
			: ret = min(ret, dp(curh, curg + 1, 1) + dis(g[curg], g[curg + 1]));
	}
	return ret;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> H >> G;
	h.resize(H);
	g.resize(G);
	for (int i = 0; i < H; i++)
		cin >> h[i].first >> h[i].second;
	for (int i = 0; i < G; i++)
		cin >> g[i].first >> g[i].second;
	memset(d, -1, sizeof(d));
	cout << dp(0, -1, 0) << "\n";
}

---

꽤나 재밌는 문제였다.

한 가지 걸리는 점은 H가 1일 때 대부분의 정답코드는 INF를 출력한다는 점이다.

https://www.acmicpc.net/board/view/76576

글 읽기 - 이 문제 H가 1이면 안되지 않나요?

재채점이 이루어질지, 아니면 어떤 조치가 취해질지 잘 예상이 되지 않는다.