반응형
문제
14890번: 경사로
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
이해 자체는 어렵지 않은 문제였다.
1. 이차원 배열에 값을 넣어주고
2. 행 / 열을 검사하면서 경사로를 놓을 수 있는지 확인한다.
경사로를 놓을 수 있는지 확인하는 과정은 다음과 같다.
1. 현재 값과 다음 값의 차를 구한다.
2-1) 차가 0인 경우 : 평지이므로 다음 구역으로 넘어간다.
2-2) 차가 1인 경우 : 현재가 더 높다. 따라서 내리막길이 필요하므로 다음 구역부터 그 다음 구역으로 가면서 내리막길을 설치할 수 있는 지 확인한다.
2-3) 차가 -1인 경우 : 현재가 더 낮다. 따라서 오르막길이 필요하므로 현재 구역부터 그 전 구역으로 가면서 오르막길을 설치할 수 있는 지 확인한다.
2-4) 그 외의 경우 : 경사로를 놓을 수 없다. 바로 false를 return한다.
경사로를 설치할 수 있는 조건은 다음과 같다.
1. 구역 범위를 만족함 (0 <= x < N)
2. 이전에 경사로를 해당 구역에 설치하지 않음
3. 경사로 시작점과 값이 같음
소스 코드
처음에 행과 열을 검사하는 조건을 따로 구현했다.
|
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int N;
int L;
int map[100][100];
bool check[100][100];
bool colCheck(int rowIdx)
{
for (int i = 0; i < N - 1; i++)
{
int cur = map[i][rowIdx];
int next = map[i + 1][rowIdx];
int sub = abs(cur - next);
if (cur == next)
continue;
else if (sub != 1)
return false;
else
{
// 위->아래
if (cur > next)
{
// 검사
for (int j = i + 1; j <= i + L; j++)
{
if (j >= N || check[j][rowIdx] || map[j][rowIdx] != next)
return false;
else
{
check[j][rowIdx] = true;
}
}
}
// 아래->위
else
{
for (int j = i; j > i - L; j--)
{
if (j < 0 || check[j][rowIdx] || map[j][rowIdx] != cur)
return false;
else
{
check[j][rowIdx] = true;
}
}
}
}
}
return true;
}
bool rowCheck(int colIdx)
{
for (int i = 0; i < N - 1; i++)
{
int cur = map[colIdx][i];
int next = map[colIdx][i + 1];
int sub = abs(cur - next);
if (cur == next)
continue;
else if (sub != 1)
return false;
else
{
// 위->아래
if (cur > next)
{
// 검사
for (int j = i + 1; j <= i + L; j++)
{
if (j >= N || check[colIdx][j] || map[colIdx][j] != next)
return false;
else
{
check[colIdx][j] = true;
}
}
}
// 아래->위
else
{
for (int j = i; j > i - L; j--)
{
if (j < 0 || check[colIdx][j] || map[colIdx][j] != cur)
return false;
else
{
check[colIdx][j] = true;
}
}
}
}
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> L;
int result = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> map[i][j];
}
}
for (int i = 0; i < N; i++)
{
if (colCheck(i))
{
result += 1;
}
}
memset(check, 0, sizeof(check));
for (int i = 0; i < N; i++)
{
if (rowCheck(i))
{
result += 1;
}
}
cout << result;
return 0;
}
|
cs |
짜고 보니 행과 열을 따로 검사하는게 마음에 안들어서, vector에 해당 행/열의 원소들을 모두 넣어주고
한 가지 방법으로 검사하는 코드를 만들었다.
|
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int N;
int L;
int map[100][100];
bool check[100];
vector<int> v;
bool IsPossible()
{
// 초기화
memset(check, false, sizeof(check));
for (int i = 0; i < N - 1; i++)
{
int cur = v[i];
int next = v[i + 1];
int sub = v[i] - v[i + 1];
// 같을 때(평지)
if (sub == 0)
continue;
// 왼쪽 경사로, 내리막길
else if (sub == 1)
{
for (int j = i + 1; j <= i + L; j++)
{
if (j >= N || check[j] || v[j] != next)
return false;
else
{
check[j] = true;
}
}
}
// 오른쪽 경사로, 오르막길
else if (sub == -1)
{
for (int j = i; j > i - L; j--)
{
if (j < 0 || check[j] || v[j] != cur)
return false;
else
{
check[j] = true;
}
}
}
// 경사로 만들어지지 못함
else
return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> L;
int result = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> map[i][j];
}
}
// 행 검사
for (int i = 0; i < N; i++)
{
v.clear();
for (int j = 0; j < N; j++)
{
v.push_back(map[i][j]);
}
if (IsPossible())
{
result += 1;
}
}
// 열 검사
for (int i = 0; i < N; i++)
{
v.clear();
for (int j = 0; j < N; j++)
{
v.push_back(map[j][i]);
}
if (IsPossible())
{
result += 1;
}
}
cout << result;
return 0;
}
|
cs |
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 2665] 미로만들기 C++ (0) | 2022.07.24 |
|---|---|
| [백준 20055] 컨베이어 벨트 위의 로봇 C++ (0) | 2022.07.12 |
| [백준 2343] 기타 레슨 C++ (0) | 2022.06.26 |
| [백준 2805] 나무 자르기 C++ (0) | 2022.06.22 |
| [백준 2667] 단지번호붙이기 C++ (0) | 2022.06.01 |