문제 : boj 14890
풀이
- 가로방향 이동을 하고, 그것을 세로방향으로 똑같이 해주면 된다.
- 왼쪽에서 오른쪽 방향으로, 위에서 아래 방향으로 움직이면서 이동이 가능한 길인지 판단한다.
- cnt : 경사로를 설치해 끝까지 이동이 가능한 길의 수(canpass가 true면 cnt가 하나 증가하고, 경사로 설치가 불가능하다고 판단되면 canpass = false가 되어 숫자를 세지 않는다.)
- 경사로의 길이가 L이상이어야 하므로 이전까지의 길이를 l에 저장해 비교한다.
- down : l이라는 하나의 변수에 값을 저장해 사용하게되면 높이가 높아지는 경우에는 바로 판단이 가능하지만 높이가 낮아지는 경우에는 낮아지고 난 이후의 길이를 l에 저장해야 한다. down이라는 변수를 통해서 down이 true이면 다음에 높이가 변할 때, 이전의 상황을 반영해 판단하게 된다.
- (1)위치는 l이 L보다 크므로 경사로를 설치할 수 있다. (3)위치는 경사로를 두개 설치해야 하므로 l이 2*L보다 길어야 하지만 짧으므로 경사로 설치가 불가능하고 따라서 이경우는 canpass가 false가 되고, break를 통해 for문에서 빠져나간다.
C++
#include <iostream>
#include <cstdio>
using namespace std;
int N, L, map[101][101];
int findpassway(){
int cnt(0), l(1); bool canpass=true, down=false;
// 가로방향 이동
for(int n(0); n < N; n++){
l=1; down=false; canpass=true;
for(int m(1); m < N; m++){
if (abs(map[n][m] - map[n][m-1]) > 1){
canpass = false;
break;
}
if(map[n][m] > map[n][m-1]){
if(l < L) {
canpass = false;
break;
}
if(down){
if(l < 2*L) {
canpass = false;
break;
}
else down=false;
}
l = 1;
}
else if(map[n][m] < map[n][m-1]){
if(down){
if(l < L){
canpass=false;
break;
}
}
if(m > N-L){
canpass = false;
break;
}
l = 1; down=true;
}
else if(map[n][m] == map[n][m-1]) l++;
}
if(canpass) cnt++;
}
// 세로방향 이동
for(int n(0); n < N; n++){
l=1; down=false; canpass=true;
for(int m(1); m < N; m++){
if (abs(map[m][n] - map[m-1][n]) > 1){
canpass = false;
break;
}
if(map[m][n] > map[m-1][n]){
if(l < L) {
canpass = false;
break;
}
if(down){
if(l < 2*L) {
canpass = false;
break;
}
else down=false;
}
l = 1;
}
else if(map[m][n] < map[m-1][n]){
if(down){
if(l < L){
canpass=false;
break;
}
}
if(m > N-L){
canpass = false;
break;
}
l = 1; down=true;
}
else if(map[m][n] == map[m-1][n]) l++;
}
if(canpass) cnt++;
}
return cnt;
}
int main(){
freopen("input.txt", "r", stdin);
cin >> N >> L;
for(int n(0); n < N; n++){
for(int m(0); m < N; m++){
cin >> map[n][m];
}
}
cout << findpassway();
fclose(stdin);
return 0;
}