백준 14890 경사로

이 문제는 각 행과,열을 길이라고 할 때 지나갈 수 있는 길의 개수를 구하는 문제입니다.

 

길을 지나간다는 것은 높이가 같은경우 통행이 가능하고 만약 높이가 정확히 1차이난다면 문제에 주어진 길이 L만큼의 경사로를 설치 할 수 있습니다. 이 경사로를 배치하면 그 구간은 지나갈 수 있게 됩니다. 이때 이 경사로는 높이가 더 낮은 곳에만 설치 할 수 있습니다.

 

즉 정리하면 각 행과 열을 훑어보면서, 높이가 1차이 나는 순간 높이가 더낮은 바닥이 최소 L이상 존재하는지 확인 해주면 되는 문제입니다.

 

구간을 보면서 현재 연속된 구간의 개수인 curlen을 추가해주며 진행해줍니다. 이때 높이가 1 차이나는 순간을 만났을 때 만약 전에 본 부분이 높이가 낮다면 curlen 이 주어진 길이 L보다 크거나 같은지 확인 해주면 되고 이후 부분이 높이가 더 낮다면 이후 부분을 쭉 훑으며 curlen 보다 크거나 같다면 curlen에 L길이를 빼준뒤 다음 구간을 진행해주면 됩니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <cmath>

using namespace std;

int board[110][110];
int N,L;
int ans;

int sol(int num, int dir) {
    int cur;
    int prev;
    int curlen = 1;
    for(int i = 0; i < N; i++) {
        if(dir==1) cur = board[num][i];
        else cur = board[i][num];

        if(i==0) prev = cur;
        else {
            if(prev == cur) {
                curlen++;
            }
            else if(abs(prev-cur) == 1) {
                if(prev-cur == -1) { //오른쪽이 더 큰 경우
                    if(curlen < L) return 0;
                    curlen = 1; // 다시 1
                    prev = cur;
                }
                else { //왼쪽이 더 큰 경우
                    curlen = 0;
                    prev = cur;
                    while(prev-cur == 0) {
                        curlen++;
                        i++;
                        if(i > N-1) break;

                        if(dir==1) cur = board[num][i];
                        else cur = board[i][num];
                    }
                    i--;

                    if(curlen < L) return 0;
                    else {
                        curlen -= L;
                    }
                }
            }
            else return 0;
        }
    }
    return 1;
}


int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> L;

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            cin >> board[i][j];

    for(int i = 0; i < N; i++) { //각 행별 확인
        int ret = sol(i, 1);
        ans += ret;

    }

    for(int i = 0; i < N; i++) { //각 열별 확인
        int ret = sol(i, 0);
        ans += ret;
    }

    cout<<ans;
    return 0;
}