https://www.acmicpc.net/problem/14890
14890번: 경사로
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
www.acmicpc.net
골드3 문제지만 생각만 잘 하면 30분이면 해결가능하다.
시간도 2초로 매우 넉넉하다..
코드는 매우 간단하다.
row와 col를 벡터로 선언하여 전달한다. 각 downhill이 가능한지 check하기 위해 복사하여 넘기는 방식으로 하였다.
Downhill_Discrimination 함수에서는 다음과 같은 과정으로 경사로가 가능한지 check한다.
bool check[100]을 선언한다.
L=2일때 앞뒤로 경사로가 겹치는 경우, 즉 내려갔다 올라가는 경우 평지가 4가 필요한데 , 4보다 적은 것을 check하기 위한것이다.
이때 내려가는 부분먼저 check한다. 높이가 2이상 차이나면 return;
line[i] - line[i+1]이 1, 즉 내려가는 방향이면 둘 수 있는지 확인한다.
확인 방식은 L개만큼 연속된 평지가 있어야 하므로 첫번째 IF문은 조건이 i+count < N 이다. index안에서만 해결
그 다음은 평지인지와 check[i+count]가 false인지 check한다.
지금 생각하니 내리막에서는 딱히 check를 할 필요가 없을거 가다.
오르막은 똑같다, 이것은 N-1부터 1까지 check한다.
논리는 모두 같다.
전체코드는 다음과 같다.
|
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
|
// 경사로
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct check_hill {
int index;
int up_down; // -1 이면 올라가는 방향 , 1 이면 내려가는 방향, 0
};
int N, L;
int MAP[100][100];
int count_res = 0;
void Downhill_Discrimination(vector<int>& line) {
// 경우의 수
// 우선 높이 차이가 2이면 return
bool check[100] = { false };
// 내려가는거 체크
for (int i = 0; i < N - 1; i++) {
if (abs(line[i] - line[i + 1]) >= 2)
return;
if (line[i] - line[i + 1] == 1) { // 내려 가는 방향이면
int level = line[i + 1];
for (int count = 1; count <= L; count++) {
if (i + count < N) {
if (level == line[i + count] && check[i+count] == false) {
check[i+count] = true;
}
else {
return;
}
}
else {
return;
}
}
}
}
// 올라가는거 체크
for (int i = N - 1; i > 0; i--) {
if (abs(line[i] - line[i - 1]) >= 2)
return;
if (line[i] - line[i - 1] == 1) {
int level = line[i - 1];
for (int count = 1; count <= L; count++) {
if (i - count > -1) {
if (level == line[i - count] && check[i - count] == false) {
check[i - count] = true;
}
else {
return;
}
}
else {
return;
}
}
}
}
count_res++;
}
void solve() {
// 행열 처리
for (int i = 0; i < N; i++) {
vector<int> row;
vector<int> col;
for (int j = 0; j < N; j++) {
row.push_back(MAP[i][j]);
col.push_back(MAP[j][i]);
}
Downhill_Discrimination(row);
Downhill_Discrimination(col);
}
cout << count_res << endl;
}
void input() {
cin >> N >> L;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> MAP[i][j];
}
void init() {
cin.tie(0)->sync_with_stdio(false);
}
int main() {
init();
input();
solve();
}
|
cs |
'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글
| [백준 19237] 어른 상어 (C++) (0) | 2021.08.21 |
|---|---|
| [백준 17090] 미로 탈출하기 (C++) (0) | 2021.08.20 |
| [백준 19236] 청소년 상어 (C++) (0) | 2021.08.19 |
| [백준 20057] 마법사 상어와 토네이도 (C++) (0) | 2021.08.18 |
| [백준 17837] 새로운 게임 2 (C++) (0) | 2021.08.17 |