https://www.acmicpc.net/problem/2873
결론부터 말하면 이 문제는 구글링으로 답을 얻었다. 며칠동안 너무 생각을 하다, 끙끙 앓는 것 보단 답지를 보는 습관을 슬슬 고쳐야할 것 같다. 내가 퍼즐게임을 즐겨하다 보니 이런 습관이 든것 같은데, 코딩테스트는 퍼즐게임과 달리 시간이 기다리지 않으니까, 앞으로는 확실하게 시간 측정을 하고, 못 풀면 빨리 답을 찾아서, 요령을 습득하자.
처음엔 쉬울 것 같다는 생각과 함게 문제에 임했다. 왜냐하면 모든 칸을 둘러보면 끝이다. 오른쪽 끝으로 갔다가, 아래로 한 칸아래, 왼쪽 끝으로 가는 것을 반복하면 답이 나오겠거니 했다. 그런데, 막상 문제에 도전해보니, 이 방법은 조건이 필요했다는 것을 깨달았다. R이 짝수, C가 짝수 인 경우는 위의 방법으로 모든 칸을 들렀다가, 목적지로 갈수 없다. 적어도 한 칸 이상은 비워야한다는 것을 알게 되었다.
그러면 어떻게 해야할까? 나는 다소 바보같은 방법을 취했었다. 모든 케이스를 둘러보겠다는 생각을 한 것이다.
당시 나는 테스트 케이스를 충분히 둘러보지 못해서 좁은 특정 위치만 한 칸을 비울 수 있다고 생각했다.
그렇게 나눈 것은 다음과 같았다.
4 x 4일 경우 나는 다음과 같은 칸들만 비울 수 있다고, 생각했다. 각 번호는 케이스 번호다.
좀 더 관찰을 했었으면 답을 구할 수 있었을 텐데, 너무 관찰을 안 한 것이 후회가 된다.
그렇게 나온 코드는..
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int R, C, P[1001][1001];
string ans = "";
char getOp(char ch)
{
if (ch == 'R') return 'L';
if (ch == 'L') return 'R';
if (ch == 'U') return 'D';
return 'U';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> R >> C;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
cin >> P[i][j];
if (R % 2 > 0)
{
char c = 'R';
for (int d = 0; d < R; d++)
{
for (int i = 0; i < C - 1; i++)
ans.push_back(c);
ans.push_back('D');
c = getOp(c);
}
ans.pop_back();
}
else if (C % 2 > 0)
{
char c = 'D';
for (int r = 0; r < C; r++)
{
for (int i = 0; i < R - 1; i++)
ans.push_back(c);
ans.push_back('R');
c = getOp(c);
}
}
else
{
vector<pair<int, int>> pos = { {P[R - 1][C - 2], 2}, {P[R - 2][C - 1], 3} };
if (C > 2) pos.push_back({ P[0][C - 1], 0 });
if (R > 2) pos.push_back({ P[R - 1][0], 1 });
pos.push_back({P[0][1], 4});
pos.push_back({P[1][0], 5});
sort(pos.begin(), pos.end());
switch (pos[0].second)
{
case 0: {
char c = 'D';
for (int r = 0; r < C - 1; r++)
{
ans.push_back(c);
ans.push_back('R');
c = getOp(c);
}
if (R > 2)
{
ans.push_back('D');
c = 'L';
for (int i = 0; i <= R - 3; i++)
{
for (int j = 0; j < C - 1; j++)
{
ans.push_back(c);
}
ans.push_back('D');
c = getOp(c);
}
ans.pop_back();
}
}
break;
case 1: {
char c = 'R';
for (int d = 0; d < R - 1; d++)
{
ans.push_back(c);
ans.push_back('D');
c = getOp(c);
}
if (C > 2)
{
ans.push_back('R');
c = 'U';
for (int i = 0; i <= C - 3; i++)
{
for (int j = 0; j < R - 1; j++)
{
ans.push_back(c);
}
ans.push_back('R');
c = getOp(c);
}
ans.pop_back();
}
}
break;
case 2: {
char c = 'D';
for (int i = 0; i <= C - 3; i++)
{
for (int j = 0; j < R - 1; j++)
{
ans.push_back(c);
}
ans.push_back('R');
c = getOp(c);
}
c = 'R';
for (int d = 0; d < R - 1; d++)
{
ans.push_back(c);
ans.push_back('D');
c = getOp(c);
}
}
break;
case 3:
{
char c = 'R';
for (int i = 0; i <= R - 3; i++)
{
for (int j = 0; j < C - 1; j++)
{
ans.push_back(c);
}
ans.push_back('D');
c = getOp(c);
}
c = 'D';
for (int r = 0; r < C - 1; r++)
{
ans.push_back(c);
ans.push_back('R');
c = getOp(c);
}
}
break;
case 4:
{
char c = 'R';
ans.push_back('D');
for (int i = 0; i <= R - 2; i++)
{
ans.push_back(c);
ans.push_back('D');
c = getOp(c);
}
ans.pop_back();
ans.push_back('R');
c = 'U';
for (int i = 0; i <= C - 3; i++)
{
for (int j = 0; j < R - 1; j++)
{
ans.push_back(c);
}
ans.push_back('R');
c = getOp(c);
}
ans.pop_back();
}
break;
default:
{
char c = 'D';
ans.push_back('R');
for (int i = 0; i <= C - 2; i++)
{
ans.push_back(c);
ans.push_back('R');
c = getOp(c);
}
ans.pop_back();
ans.push_back('D');
c = 'L';
for (int i = 0; i <= R - 3; i++)
{
for (int j = 0; j < C - 1; j++)
{
ans.push_back(c);
}
ans.push_back('D');
c = getOp(c);
}
ans.pop_back();
}
break;
}
}
cout << ans << '\n';
}유지보수, 리팩토링 등을 전혀 고려하지 않은 코드가 나와버렸다. 이 코드를 짠 나조차도 읽기가 힘들다. 당연하겠지만 틀렸다. 이후 며칠간 머리를 싸맸지만, 답이 떠오르지 않았던 나는 결국 구글링을 거쳤다.
알고리즘(C++) / 백준 2873 : 롤러코스터
2873 www.acmicpc.net/problem/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른
se-jung-h.tistory.com
비울 수 있는 칸은 다음과 같다.
즉, 열 번호 + 행 번호 가 홀수 인 경우를 고려하면 된다.
위의 코드는 내가 규칙성을 발견하지 못해서, 복잡하게 되었지만, 규칙을 발견한 이상, 더 코드를 간단하게 구성할 수 있게 되었다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int R, C, P[1001][1001];
string ans = "";
char getOp(char ch)
{
if (ch == 'R') return 'L';
if (ch == 'L') return 'R';
if (ch == 'U') return 'D';
return 'U';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> R >> C;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
cin >> P[i][j];
if (R % 2 > 0)
{
char c = 'R';
for (int d = 0; d < R; d++)
{
for (int i = 0; i < C - 1; i++)
ans.push_back(c);
ans.push_back('D');
c = getOp(c);
}
ans.pop_back();
}
else if (C % 2 > 0)
{
char c = 'D';
for (int r = 0; r < C; r++)
{
for (int i = 0; i < R - 1; i++)
ans.push_back(c);
ans.push_back('R');
c = getOp(c);
}
ans.pop_back();
}
else
{
int tr = 0, tc = 0, m = 1001;
for(int y = 0; y < R; y++)
for(int x = 0; x < C; x++)
if (m > P[y][x] && (y + x) % 2 == 1)
{
m = P[y][x];
tr = y; tc = x;
}
char c = 'R';
for (int r = 0; r < R; r += 2)
{
bool f = false;
if (r <= tr && tr <= r + 1)
{
char d = 'D';
int y = r, x = 0;
for (int j = 0; j < C - 1; j++)
{
for (int i = 0; i < 2 && j < C - 1; i++)
{
if (i == 0)
{
y += ((d == 'D') ? 1 : -1);
if (tr == y && tc == x)
{
if (c == 'R') ++x;
else --x;
ans.push_back(c);
++j;
}
ans.push_back(d);
d = getOp(d);
}
else
{
if (c == 'L') --x;
else ++x;
ans.push_back(c);
}
}
}
f = true;
if (y < R - 1)
{
ans.push_back('D');
if(y % 2 == 0 && r + 2 < R) ans.push_back('D');
}
}
else
{
for (int i = 0; i < C - 1; i++)
ans.push_back(c);
ans.push_back('D');
for (int i = 0; i < C - 1; i++)
ans.push_back(getOp(c));
if (r + 2 < R)
{
ans.push_back('D');
}
}
if (f) c = 'L';
}
}
cout << ans << '\n';
}
블로그 글의 코드를 안 보고, 개념만 보고, 코드를 구성했는데, 블로그의 코드보다 더 복잡해졌다. 디버깅에도 시간을 많이 소요해버렸는데, 코딩 테스트에 이 문제가 나왔다면 그냥 틀린 문제다. 앞으론 너무 전전긍긍하지말도록 하자.
'알고리즘 문제 풀이 일지' 카테고리의 다른 글
| 백준 1060: 좋은 수 (0) | 2024.10.05 |
|---|---|
| 백준 5588: 별자리 찾기 (0) | 2024.10.03 |
| 백준 2647: 검은점과 하얀점의 연결 (0) | 2024.09.26 |
| 백준 23268: Deceptive Directions (0) | 2024.09.20 |
| 백준 2795: 사업 확장 (0) | 2024.09.18 |
