문제 링크 : https://www.acmicpc.net/problem/2873
2873번: 롤러코스터
문제 상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다. 어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다. 이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가
www.acmicpc.net
문제
상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.
어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.
이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.
각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 둘째 줄부터 R개 줄에는 각 칸을 지나갈 때 얻을 수 있는 기쁨이 주어진다. 이 값은 1000보다 작은 양의 정수이다.
출력
첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답은 여러 가지 일 수도 있다.
풀이
사실 이 문제는 풀다가 가장 중요한 부분을 해결하지 못해서 백준님 코드를 보았다 ㅠㅠ
코드를 보면서 사람이 이렇게 생각할 수도 있구나.. 하고 많이 놀랐던 문제이다.
우선 이 문제를 해결하기 위해선 최대한 많은 칸을 방문하는 것이 우선이다. 모든 칸이 양수의 기쁨이므로 많이 갈수록 이득이기 때문이다.
문제를 풀 때 3가지 케이스가 있는데,
1. R(세로줄)이 홀수일 때
2. C(가로줄)이 홀수일 때
3. 둘 다 짝수일 때
1.
세로줄이 홀수일 때 반드시 이런 식으로 모든 칸을 방문할 수 있다.
2.
가로줄이 홀수일 때는 이런식으로 모든 칸을 방문할 수 있다.
3. 예상했다시피 문제는 3번째 경우이다.
이 경우 반드시 "한 칸"이상 방문하지 않는 경로가 생긴다.
왜 그러냐 하면...
이런 짝수 x 짝수 행렬 모양의 체스판이 있다고 하자.
문제의 조건대로 좌측 맨 위 검은색에서 우측 맨 아래 검은색으로 가야 하는데,
모든 칸을 이동하기 위해선 짝수 x 짝수 -1번 움직인 후 검은색에 도착해야 한다.
하지만, 위 그림대로라면 검은색에서 출발하여 검은색으로 가려면 반드시 짝수번 움직여야 한다.
따라서 반드시 "한 칸"은 포기해야 한다.
그러면 당연히 가장 기쁨의 농도가 낮은 칸을 포기하는 게 올바른 방향이겠다.
그렇다면 가장 작은 칸을 버리고 생각해보자.
여기서 버릴 때에도 잘 생각하고 버려야 한다!!! 방금 막 버리다가 30분 동안 그린 거 다 지웠다
위에서 본 체스판에서 "한 칸"을 버릴 때 검은색~검은색으로 가는데 검은색을 버려버린다면 구석을 들어갈 수 없어서
최소 두 칸 이상(반드시 흰색 포함) 손해가 생겨버린다. 따라서 흰색(가로 + 세로 % 2 = 1) 중 가장 낮은 기쁨 칸을 버려야 한다.
그렇다면 버린 후 순회하는 과정을 그림으로 살펴보자.
위 그림처럼 시작과 끝부분에 사람을 두어 서로 움직여 만난다고 생각해보자.
(초록색 부분은 포기한 칸)
그림을 보면 공백이 너무 많은 것 같다. 축소시킬 순 없을까?
귀신같이 행렬이 축소되었다!!
계속해보자
짜잔! 드디어 조금 풀만해진 것 같다.
여기서 또 축소시킬 순 없을까? 당연히 할 수 있다
위에서 했던 과정을 좌-우로 적용시켜보자
이런 식으로 축소시킬 수 있다.
최종 결과는 위의 그림 또는 녹색 칠이 오른쪽 위에 있는 경우이다. 이 부분은 마지막에 처리해주면 되겠다.
코드를 보자
소스 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int happy[1001][1001];
int r, c;
string ans;
void append(string& ans, char c, int cnt) {
for (int i = 0; i < cnt; i++) {
ans += c;
}
}
void side() {
int mul = r * c - 1;
int x = 0, y = 0;
int dir = 0; // 0: 동 1: 북 2: 서 3: 남
while (mul--) {
if (dir == 0 && x + 1 < c) { // -->
x++;
ans.push_back('R');
}
else if (dir == 0 && x + 1 == c) { // 우측 끝
y++;
ans.push_back('D');
dir = 3;
}
else if (dir == 2 && x - 1 >= 0) { // <--
x--;
ans.push_back('L');
}
else if (dir == 2 && x - 1 == -1) { // 좌측 끝
y++;
ans.push_back('D');
dir = 3;
}
else if (dir == 3 && x + 1 == c) { //우측 경계
x--;
ans.push_back('L');
dir = 2;
}
else if (dir == 3 && x - 1 == -1) { //좌측 경계
x++;
ans.push_back('R');
dir = 0;
}
}
}
|
cs |
side 함수는 케이스 1을 처리한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
void up_down() {
int mul = r * c - 1;
int x = 0, y = 0;
int dir = 3; // 0: 동 1: 북 2: 서 3: 남
while (mul--) {
if (dir == 3 && y + 1 < r) { // up
y++;
ans.push_back('D');
}
else if (dir == 3 && y + 1 == r) { // 아래 끝
x++;
ans.push_back('R');
dir = 0;
}
else if (dir == 1 && y - 1 >= 0) { // down
y--;
ans.push_back('U');
}
else if (dir == 1 && y - 1 == -1) { // 윗쪽 끝
x++;
ans.push_back('R');
dir = 0;
}
else if (dir == 0 && y + 1 == r) { //아래측 경계
y--;
ans.push_back('U');
dir = 1;
}
else if (dir == 0 && y - 1 == -1) { //위측 경계
y++;
ans.push_back('D');
dir = 3;
}
}
}
|
cs |
up_down 함수는 case 2를 처리한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
void couple() {
int x, y;
x = 0;
y = 1;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if ((i + j) % 2 == 1) {
if (happy[x][y] > happy[i][j]) {
x = i;
y = j;
}
}
}
}
int x1 = 0;
int y1 = 0;
int x2 = r - 1;
int y2 = c - 1;
string ans2 = "";
while (x2 - x1 > 1) {
if (x1 / 2 < x / 2) {
append(ans, 'R', c - 1);
append(ans, 'D', 1);
append(ans, 'L', c - 1);
append(ans, 'D', 1);
x1 += 2;
}
if (x / 2 < x2 / 2) {
append(ans2, 'R', c - 1);
append(ans2, 'D', 1);
append(ans2, 'L', c - 1);
append(ans2, 'D', 1);
x2 -= 2;
}
}
while (y2 - y1 > 1) {
if (y1 / 2 < y / 2) {
append(ans, 'D', 1);
append(ans, 'R', 1);
append(ans, 'U', 1);
append(ans, 'R', 1);
y1 += 2;
}
if (y / 2 < y2 / 2) {
append(ans2, 'D', 1);
append(ans2, 'R', 1);
append(ans2, 'U', 1);
append(ans2, 'R', 1);
y2 -= 2;
}
}
if (y == y1) {
append(ans, 'R', 1);
append(ans, 'D', 1);
}
else {
append(ans, 'D', 1);
append(ans, 'R', 1);
}
reverse(ans2.begin(), ans2.end());
ans += ans2;
}
|
cs |
가장 중요한 couple 함수이다.
가장 먼저, 버릴 칸을 찾고
위 설명대로 위아래 or 좌우를 자르면서 그 과정을 간단하게 문자열로 변환한다.
끝부분의 사람 좌표를 (x2, y2)로 둔 후 string ans2에 지나온 길들을 문자열로 넣고 이후에 뒤집어준다.(실제로는 하나만 움직이는 것이므로)
append 함수는 따로 만든 함수인데, 원하는 string에 원하는 문자를 원하는 수만큼 push_back 한다고 보면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int main()
{
scanf("%d%d", &r, &c);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
scanf("%d", &happy[i][j]);
}
}
if (r % 2 == 1) {
side();
cout << ans;
}
else if (c % 2 == 1) {
up_down();
cout << ans;
}
else {
couple();
cout << ans;
}
return 0;
}
|
cs |
main함수이다.
문제 번호 위에 난이도가 설명하듯 아직 내가 풀기엔 많이 어려운 문제였다.
백준님 코드와 설명을 많이 참조하긴 했지만 문제를 풀면서 많이 배울 수 있었다.
개발환경 : Visual Studio 2019
지적, 조언 언제든지 환영입니다~~
'백준 문제풀이' 카테고리의 다른 글
| 백준 1780번 종이의 개수 (0) | 2020.01.02 |
|---|---|
| 백준 11728번 배열 합치기 (0) | 2020.01.02 |
| 백준 1080번 행렬 (0) | 2020.01.02 |
| 백준 1783번 병든 나이트 (0) | 2020.01.01 |
| 백준 2875번 대회 or 인턴 (0) | 2020.01.01 |