백준 2618번
오늘 풀어본 문제는 백준의 2618번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
어떤 도시의 중심가는 $N$ 개의 동서방향 도로와 $N$ 개의 남북방향 도로로 구성되어 있다.
모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 $1$ 에서 시작하여 $N$ 까지 번호가 할당되어 있고 동서방향 도로는 위부터 $1$ 에서 시작하여 $N$ 까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 $1$ 이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 $(\text{동서방향 도로 번호}, \text{남북방향 도로 번호})$ 로 나타낸다. $N$ 이 $6$ 인 경우의 예를 들면 다음과 같다.
이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 $(1, 1)$ 의 위치에 있고 경찰차2는 $(N, N)$ 의 위치에 있다. 경찰 본부에서는 처리할 사건이 있으면 그 사건이 발생된 위치를 두 대의 경찰차 중 하나에 알려 주고, 연락 받은 경찰차는 그 위치로 가장 빠른 길을 통해 이동하여 사건을 처리한다. (하나의 사건은 한 대의 경찰차가 처리한다.) 그리고 사건을 처리 한 경찰차는 경찰 본부로부터 다음 연락이 올 때까지 처리한 사건이 발생한 위치에서 기다린다. 경찰 본부에서는 사건이 발생한 순서대로 두 대의 경찰차에 맡기려고 한다. 처리해야 될 사건들은 항상 교차로에서 발생하며 경찰 본부에서는 이러한 사건들을 나누어 두 대의 경찰차에 맡기되, 두 대의 경찰차들이 이동하는 거리의 합을 최소화 하도록 사건을 맡기려고 한다.
예를 들어 앞의 그림처럼 $N=6$ 인 경우, 처리해야 하는 사건들이 $3$ 개 있고 그 사건들이 발생된 위치 를 순서대로 $(3, 5)$, $(5, 5)$, $(2, 3)$ 이라고 하자. $(3, 5)$ 의 사건을 경찰차2에 맡기고 $(5, 5)$ 의 사건도 경찰차2에 맡기며, $(2, 3)$ 의 사건을 경찰차1에 맡기면 두 차가 이동한 거리의 합은 $4 + 2 + 3 = 9$ 가 되 고, 더 이상 줄일 수는 없다.
처리해야 할 사건들이 순서대로 주어질 때, 두 대의 경찰차가 이동하는 거리의 합을 최소화 하도록 사건들을 맡기는 프로그램을 작성하시오.
입력
첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 $N$ $(5 \le N \le 1,000)$ 이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 $W$ $(1 \le W \le 1,000)$ 가 주어진다. 셋째 줄부터 $(W+2)$ 번째 줄까지 사건이 발생된 위치가 한 줄에 하나씩 주어진다. 경찰차들은 이 사건들을 주어진 순서대로 처리해야 한다. 각 위치는 동서방향 도로 번호를 나타내는 정수와 남북방향 도로 번호를 나타내는 정수로 주어지며 두 정수 사이에는 빈칸이 하나 있다. 두 사건이 발생한 위치가 같을 수 있다.
출력
첫째 줄에 두 경찰차가 이동한 총 거리를 출력한다. 둘째 줄부터 시작하여 $(i+1)$ 번째 줄에 $i$ $(1 \le i \le W)$ 번째 사건이 맡겨진 경찰차 번호 $1$ 또는 $2$ 를 출력한다.
풀이과정
1번째 시도
문제를 해결하기 위해 DP 를 이용했다.
2차원 배열을 이용하여, 각 인덱스가 경찰차1과 경찰차2가 마지막으로 맡았던 사건의 번호가 되도록 하였을 때, 그렇게 되기 위해 필요한 최소 이동거리를 저장하게 하는 방식이었다.
코드는 다음과 같이 작성하였다.
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
ll dist(const pll& A, const pll& B);
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, W;
cin >> N >> W;
vector<pll> locations1(W+1);
vector<pll> locations2(W+1);
locations1[0] = make_pair(1, 1);
locations2[0] = make_pair(N, N);
for (ll i=1; i<=W; i++) {
cin >> locations1[i].first >> locations1[i].second;
locations2[i] = locations1[i];
}
vector<vector<pair<ll, pll>>> dp(W+1, vector<pair<ll, pll>>(W+1, make_pair(10'000'000LL, make_pair<ll, ll>(0, 0))));
dp[0][0].first = 0;
dp[0][0].second = make_pair(0, 0);
dp[1][0].first = dist(make_pair(1, 1), locations1[1]);
dp[1][0].second = make_pair(0, 0);
for (ll i=2; i<=W; i++) {
dp[i][0].first = dp[i-1][0].first + dist(locations1[i-1], locations1[i]);
dp[i][0].second = make_pair(i-1, 0);
}
dp[0][1].first = dist(make_pair(N, N), locations2[1]);
dp[0][1].second = make_pair(0, 0);
for (ll i=2; i<=W; i++) {
dp[0][i].first = dp[0][i-1].first + dist(locations2[i-1], locations2[i]);
dp[0][i].second = make_pair(0, i-1);
}
for (ll sum=3; sum<2 * W; sum++) {
for (ll first=1; first<sum; first++) {
ll second = sum - first;
if (first > W || second > W) {
continue;
}
if (first > second) {
if (first - second == 1) {
for (ll start=0; start<=first-2; start++) {
ll candidate = dp[start][second].first + dist(locations1[start], locations1[first]);
if (dp[first][second].first > candidate) {
dp[first][second].first = candidate;
dp[first][second].second = make_pair(start, second);
}
}
}
else {
dp[first][second].first = dp[first-1][second].first + dist(locations1[first-1], locations1[first]);
dp[first][second].second = make_pair(first-1, second);
}
}
else if (first < second) {
if (second - first == 1) {
for (ll start=0; start<=second-2; start++) {
ll candidate = dp[first][start].first + dist(locations2[start], locations2[second]);
if (dp[first][second].first > candidate) {
dp[first][second].first = candidate;
dp[first][second].second = make_pair(first, start);
}
}
}
else {
dp[first][second].first = dp[first][second-1].first + dist(locations2[second-1], locations2[second]);
dp[first][second].second = make_pair(first, second-1);
}
}
}
}
ll minimum = LLONG_MAX;
pll curr;
for (ll i=0; i<W; i++) {
if (minimum > dp[W][i].first) {
minimum = dp[W][i].first;
curr = make_pair(W, i);
}
}
for (ll i=0; i<W; i++) {
if (minimum > dp[i][W].first) {
minimum = dp[i][W].first;
curr = make_pair(i, W);
}
}
stack<pll> s;
s.push(curr);
curr = dp[curr.first][curr.second].second;
while (curr.first != 0 || curr.second != 0) {
s.push(curr);
curr = dp[curr.first][curr.second].second;
}
cout << minimum << '\n';
ll first = 0;
ll second = 0;
while (!s.empty()) {
auto curr = s.top();
s.pop();
if (first != curr.first) {
cout << 1 << '\n';
}
else {
cout << 2 << '\n';
}
}
return 0;
}
ll dist(const pll& A, const pll& B) {
return abs(A.first - B.first) + abs(A.second - B.second);
}
실행 결과 ‘틀렸습니다’ 가 떴다.
2번째 시도
질문 게시판의 반례들을 찾아 테스트 해본 결과, 거리는 정확하게 계산해냈지만 어떤 경찰차가 움직여야 하는지 제대로 추적하지 못하고 있었다.
사용한 추적 방식은 DP 테이블을 업데이트 하는 과정에서 최소 값이 반영되기 위한 이전의 DP 테이블의 위치를 같이 저장해두는 것이었는데, DP 테이블 업데이트가 모두 끝나고 사건별 이동 경찰차를 추적하는 과정에서 다음에 확인해야 할 DP 테이블의 인덱스를 업데이트 해주지 않아 문제가 발생했던 것이다.
코드는 다음과 같이 수정하였다.
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
ll dist(const pll& A, const pll& B);
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, W;
cin >> N >> W;
vector<pll> locations1(W+1);
vector<pll> locations2(W+1);
locations1[0] = make_pair(1, 1);
locations2[0] = make_pair(N, N);
for (ll i=1; i<=W; i++) {
cin >> locations1[i].first >> locations1[i].second;
locations2[i] = locations1[i];
}
vector<vector<pair<ll, pll>>> dp(W+1, vector<pair<ll, pll>>(W+1, make_pair(10'000'000LL, make_pair<ll, ll>(0, 0))));
dp[0][0].first = 0;
dp[0][0].second = make_pair(0, 0);
dp[1][0].first = dist(make_pair(1, 1), locations1[1]);
dp[1][0].second = make_pair(0, 0);
for (ll i=2; i<=W; i++) {
dp[i][0].first = dp[i-1][0].first + dist(locations1[i-1], locations1[i]);
dp[i][0].second = make_pair(i-1, 0);
}
dp[0][1].first = dist(make_pair(N, N), locations2[1]);
dp[0][1].second = make_pair(0, 0);
for (ll i=2; i<=W; i++) {
dp[0][i].first = dp[0][i-1].first + dist(locations2[i-1], locations2[i]);
dp[0][i].second = make_pair(0, i-1);
}
for (ll sum=3; sum<2 * W; sum++) {
for (ll first=1; first<sum; first++) {
ll second = sum - first;
if (first > W || second > W) {
continue;
}
if (first > second) {
if (first - second == 1) {
for (ll start=0; start<=first-2; start++) {
ll candidate = dp[start][second].first + dist(locations1[start], locations1[first]);
if (dp[first][second].first > candidate) {
dp[first][second].first = candidate;
dp[first][second].second = make_pair(start, second);
}
}
}
else {
dp[first][second].first = dp[first-1][second].first + dist(locations1[first-1], locations1[first]);
dp[first][second].second = make_pair(first-1, second);
}
}
else if (first < second) {
if (second - first == 1) {
for (ll start=0; start<=second-2; start++) {
ll candidate = dp[first][start].first + dist(locations2[start], locations2[second]);
if (dp[first][second].first > candidate) {
dp[first][second].first = candidate;
dp[first][second].second = make_pair(first, start);
}
}
}
else {
dp[first][second].first = dp[first][second-1].first + dist(locations2[second-1], locations2[second]);
dp[first][second].second = make_pair(first, second-1);
}
}
}
}
ll minimum = LLONG_MAX;
pll curr;
for (ll i=0; i<W; i++) {
if (minimum > dp[W][i].first) {
minimum = dp[W][i].first;
curr = make_pair(W, i);
}
}
for (ll i=0; i<W; i++) {
if (minimum > dp[i][W].first) {
minimum = dp[i][W].first;
curr = make_pair(i, W);
}
}
stack<pll> s;
s.push(curr);
curr = dp[curr.first][curr.second].second;
while (curr.first != 0 || curr.second != 0) {
s.push(curr);
curr = dp[curr.first][curr.second].second;
}
cout << minimum << '\n';
ll first = 0;
ll second = 0;
while (!s.empty()) {
auto curr = s.top();
s.pop();
if (first != curr.first) {
cout << 1 << '\n';
}
else {
cout << 2 << '\n';
}
first = curr.first;
second = curr.second;
}
return 0;
}
ll dist(const pll& A, const pll& B) {
return abs(A.first - B.first) + abs(A.second - B.second);
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
꽤 오랜 시간 동안 솔브드 클래스 문제를 풀지 않았다. CLASS 문제를 미는 이 과정에 회의가 들었기 때문이다.
최근에는 수학을 제일 많이 공부했지만, 어디까지나 최대 관심사는 AI 이다. 수학을 심도있게 공부하는 것도 AI 연구를 위한 것이다. 그러나, CLASS 문제들을 미는 것이 과연 AI 연구에 큰 도움이 되는가 하는 생각이 들기 시작했다.
솔직히 CLASS 6 이상의 문제들은 프로그래머로써 알아야 할 기본적인 알고리즘의 범위를 벗어나는 것들을 다룬다고 생각한다. 그렇기 때문에 다른 공부 시간을 깎아가며 무리하게 CLASS 문제들이 비교적 불필요하게 느껴졌고, 한 동안 CLASS 문제들을 푸는 것을 중단했다. 그냥 매일 브론즈 5~3 정도 난이도의 쉬운 문제들만 풀어 스트릭만 간신히 이어가는 방식으로 가볍게 맥을 이어오고 있었다.
그러다 훈련 때문에 한 번 스트릭이 끊어진 적이 있었다. 그 이후로는 군대 내에서 스트릭이 큰 의미가 있나 하는 생각이 들었고, 최근 들어서는 스트릭에 전혀 신경을 쓰지 않게 되었다. 길어봐야 10분이면 다 푸는 간단한 문제들을 기계적으로 푸는데 지쳤기 때문이다.
그래서 앞으로는 스트릭은 신경끄고 CLASS 문제들을 미는데 코딩 공부 시간을 쓰기로 했다. 단, 앞서 이야기 한 것처럼 주 관심 분야인 AI 와는 거리가 있는 내용들을 다루고 있기 때문에 풀다가 잘 안되면 중단하고 다른 할 일을 하고, 다음 날 다시 시도해보는 방식으로 진행할 것 같다. 오늘 풀어 낸 2618번 문제가 그런 방식으로 풀린 첫 번째 문제였다.
문제 자체에 대한 이야기를 하자면, 습격자 초라기 정도는 아니었지만 꽤 머리 좀 써야 했던 골치아픈 DP 문제였던 것 같다. DP 테이블 구성 방식이나 점화식에 대한 아이디어를 떠올리는 것은 비교적 수월했지만, 그걸 코딩으로 구현하는게 조금 까다로웠던 것 같다. 확실히 CLASS 6 의 DP 문제는 격이 다르다는 걸 떠올리게 해주는 문제였다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/2618