[BOJ][2873] 롤러코스터
Updated:
1. 문제 링크
https://www.acmicpc.net/problem/2873
2. 사용 알고리즘
그리디
3. 풀이
1) R이 홀수인 경우 : 모든 칸 방문가능
2) C가 홀수인 경우 : 모든 칸 방문가능
3) R, C가 짝수인 경우 : 모든 칸 방문 불가능
- 출발, 도착칸을 흰색으로 하여 흰색과 검은색이 번갈아가면서 존재한다고 했을 때, 숫가자 가장 작은 검은색 한칸을 제외하고 나머지 모든 칸 방문 가능
4. 소스 코드
4-1. C++
https://github.com/dev-aiden/problem-solving/blob/main/boj/2873.cpp
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
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
using namespace std;
int arr[1003][1003];
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int r, c; cin >> r >> c;
int min_val = 9999, min_r, min_c;
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
cin >> arr[i][j];
if ((i + j) % 2 == 1 && min_val > arr[i][j]) {
min_val = arr[i][j];
min_r = i;
min_c = j;
}
}
}
if (r % 2 != 0) {
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c - 1; ++j) {
if (i % 2 == 0) cout << "R";
else cout << "L";
}
if (i != r - 1) cout << "D";
}
}
else if (c % 2 != 0) {
for (int i = 0; i < c; ++i) {
for (int j = 0; j < r - 1; ++j) {
if (i % 2 == 0) cout << "D";
else cout << "U";
}
if (i != c - 1) cout << "R";
}
}
else {
int row = min_r % 2 ? min_r - 1 : min_r;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < c - 1; ++j) {
if (i % 2 == 0) cout << "R";
else cout << "L";
}
if (i != r - 1) cout << "D";
}
bool flag = true;
for (int i = 0; i < c; ++i) {
for (int j = row; j < row + 1; ++j) {
if (i == min_c) {
continue;
}
else {
if (flag) cout << "D";
else cout << "U";
flag = !flag;
}
}
if (i != c - 1) cout << "R";
}
row += 2;
if (row < r) cout << "D";
for (int i = row; i < r; ++i) {
for (int j = 0; j < c - 1; ++j) {
if (i % 2 == 0) cout << "L";
else cout << "R";
}
if (i != r - 1) cout << "D";
}
}
return 0;
}
4-2. JAVA
https://github.com/dev-aiden/problem-solving/blob/main/boj/2873.java
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int arr[][] = new int[1003][1003];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int minVal = 9999, minRow = 0, minCol = 0;
for (int i = 0; i < r; ++i) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < c; ++j) {
arr[i][j] = Integer.parseInt(st.nextToken());
if ((i + j) % 2 == 1 && minVal > arr[i][j]) {
minVal = arr[i][j];
minRow = i;
minCol = j;
}
}
}
StringBuilder sb = new StringBuilder();
if (r % 2 != 0) {
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c - 1; ++j) {
if (i % 2 == 0) sb.append("R");
else sb.append("L");
}
if(i != r - 1) sb.append("D");
}
} else if (c % 2 != 0) {
for (int i = 0; i < c; ++i) {
for(int j = 0; j < r - 1; ++j) {
if (i % 2 == 0) sb.append("D");
else sb.append("U");
}
if (i != c - 1) sb.append("R");
}
} else {
int row = (minRow % 2 == 1) ? minRow - 1 : minRow;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < c - 1; ++j) {
if (i % 2 == 0) sb.append("R");
else sb.append("L");
}
if (i != r - 1) sb.append("D");
}
boolean flag = true;
for (int i = 0; i < c; ++i) {
for (int j = row; j < row + 1; ++j) {
if (i == minCol) {
continue;
} else {
if (flag) sb.append("D");
else sb.append("U");
flag = !flag;
}
}
if (i != c - 1) sb.append("R");
}
row += 2;
if(row < r) sb.append("D");
for (int i = row; i < r; ++i) {
for (int j = 0; j < c - 1; ++j) {
if (i % 2 == 0) sb.append("L");
else sb.append("R");
}
if (i != r - 1) sb.append("D");
}
}
sb.append("\n");
System.out.println(sb);
}
}
Leave a comment