1) 문제 분석
각 행과 열이 조건을 만족하는 지 고려하면 된다:
1) 높이가 전부 같다
2) 높이가 전부 같지 않다면,
(1) 높이가 달라질 때 높이 차이가 1이 아니라면 그 길을 지나갈 수 없다
(2) 높이 차이가 1일 때 낮은 쪽이 L 이상 있어야 한다.
한 행/열의 원소를 처음부터 쭉 읽어나간다. 이 때 같은 높이가 연속되는 횟수를 기억한다. 그러다가 높이가 바뀌었을 때 차이가 1이 아니라면 경사로를 놓아도 지나갈 수 없기 때문에 이 행/열은 건너뛴다. 높이가 바뀌었을 때 이전의 칸들이 낮은 쪽이라면 L길이의 경사로를 놓을 수 있는 지 확인한다. 이전의 칸들이 높은 쪽이라면, 다음에 오는 낮은 칸들이 L 길이만큼 연속적으로 있는 지 확인한다. 만약 그러하다면, 경사로를 놓을 수 있으며, 경사로를 놓은 칸들 다음에 같은 높이의 칸이 있더라도 새롭게 연속 횟수를 센다. 생각만 하면 쉬운 문제 같아보이지만 코드로 구현하는 것이 생각보다 까다로워서 쉽게 해결하지 못했다.
*이러한 문제는 앞에서 서술한 것처럼 조건을 차근차근 따져나가면서 꼼꼼히 보는 수 밖에 없는 것 같다. 이 때 처음에 한 열/행을 다 돌면 지나갈 수 있는 길로 생각하도록 코드를 짰는데, 예제3의 마지막 열처럼 조건을 만족시키지는 못했지만 열의 끝까지 도달한 경우에도 지나갈 수 있는 길로 체크하는 오류가 발생하였다. 따라서 항상 따로 플래그 변수를 두어서 확인하는 것이 좋은 습관일 듯 하다.
2) 코드
#include <iostream>
using namespace std;
int main(){
int N; //size of the map
int L; //length of a ramp
int** map; //shows height of each space
int count; //number of contiguous spaces with the same height
int path; //number of passable paths
bool avail; //false if not passable
//get input
cin >> N;
cin >> L;
map = new int*[N];
//initialize map
for(int i=0; i<N; i++){
map[i] = new int[N];
for(int j=0; j<N; j++)
cin >> map[i][j];
}
path = 0;
//check each row if it's passable or not
for(int i=0; i<N; i++){
//initialize
count = 1; avail = true; //start comparing the second element with the first element
//keep comparing the heights of two neighbouring spaces
for(int j=1 ;j<N;j++){
//if the two are of the same height
if(map[i][j]==map[i][j-1])
//count up
count++;
//if map[i][j] is higher than map[i][j-1] and there is enough space to put a ramp of length L
else if(map[i][j]-1==map[i][j-1] && count>=L)
//ramp can be installed, start counting new consecutive spaces with the same height
count = 1;
//if map[i][j] is lower than map[i][j-1]
else if(map[i][j]+1==map[i][j-1]){
//check if a ramp can be installed
//count the number of consecutive spaces with the same height as map[i][j-1]
count = 1;
while(++j<N && map[i][j]==map[i][j-1])
count++;
//can install a new ramp
if(count>=L) {
//delete the number of spaces required to install the ramp
count -= L;
j--;
}
//cannot install a new ramp
else {
//this path is not passable
avail = false;
break;
}
}
//if the heights are different and cannot be adjusted by putting a ramp
else {
//this path is not passable
avail = false;
break;
}
}
//count passable paths
if(avail)
path++;
}
//check each col if it's passable or not (same as above)
for(int j=0; j<N; j++){
count = 1; avail = true;
for(int i=1; i<N; i++){
if(map[i][j]==map[i-1][j])
count++;
else if(map[i][j]-1==map[i-1][j] && count>=L)
count = 1;
else if(map[i][j]+1==map[i-1][j]){
count = 1;
while(++i<N && map[i][j]==map[i-1][j])
count++;
if(count>=L) {
count -= L;
i--;
}
else {
avail = false;
break;
}
}
else {
avail = false;
break;
}
}
//count passable paths
if(avail)
path++;
}
//print out the result
cout << path;
}