경사로

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
// 1105 ~ 1247
int N, L, ans;
int board[101][101];
bool horizon(int i){
    int prev = board[i][0];
    bool flag = true;
    int preCnt = 1;
    bool check[N];
    fill(check, check+N, false);
    for(int a=1;a<N;a++)
    {
        if(abs(prev - board[i][a]) > 1){
            flag = false;
            break;
        }
        if(board[i][a] > prev){
            if(preCnt >= L){
                preCnt = 1;
            } 
            else{
                flag = false;
                break;
            }
        }else if(board[i][a] < prev){
            // board[i][a] 값이 앞으로 최소 L-1개는 있어야 함
            int cnt=0;
            for(int q=a;q<N;q++)
            {
                if(cnt >= L) break;
                if(board[i][q] != board[i][a]) break;
                else cnt++;
            }
            if(cnt < L){
                flag = false;
                break;
            }
            /* 현재 포함 L개는 경사로를 만드는데 사용했으므로 수를 줄여야함 */
            preCnt = -L+1;
        }else{
            // 같은 경우
            preCnt++;
        }
        prev = board[i][a];
    }
    if(flag == true) return true;
    else return false;
}
bool vertical(int i){
    int prev = board[0][i];
    bool flag = true;
    int preCnt = 1;
    bool check[N];
    fill(check, check+N, false);
    for(int a=1;a<N;a++)
    {
        if(abs(prev - board[a][i]) > 1){
            flag = false;
            break;
        }
        if(board[a][i] > prev){
            if(preCnt >= L){
                preCnt = 1;
            } 
            else{
                flag = false;
                break;
            }
        }else if(board[a][i] < prev){
            // board[i][a] 값이 앞으로 최소 L-1개는 있어야 함
            int cnt=0;
            for(int q=a;q<N;q++)
            {
                if(cnt >= L) break;
                if(board[q][i] != board[a][i]) break;
                else {
                    check[q] = true;
                    cnt++;
                }
            }
            if(cnt < L){
                flag = false;
                break;
            }
            /* 현재 포함 L개는 경사로를 만드는데 사용했으므로 수를 줄여야함 */
            preCnt = -L+1;
        }else{
            // 같은 경우
            preCnt++;
        }
        prev = board[a][i];
    }
    if(flag == true) return true;
    else return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.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++)
    {
        /* 가로 검사  */
        bool flagH = horizon(i);
        if(flagH) ans++;
        /* 세로 검사 */
        bool flagV = vertical(i);
        if(flagV) ans++;
    }
    cout << ans;
    return 0;
}

• 핵심 로직
  • 이전 블록의 값인 prev와 다음 블록의 값을 비교해서 큰 경우와 작은 경우로 나누어서 처리
    (값의 차가 1 이상이면 경사로를 놓을 수 없으니 바로 종료)
  • 작은 경우
    • 작은쪽에 경사로를 놓아야 하기 때문에 다음 블록을 포함해 앞으로 최소 L개의 같은 값이 있어야 함
      (반복문을 통해서 앞으로 L-1개가 다음 블록의 값과 일치하는지 검사)
    • 현재까지 연속된 같은 블록을 세는 preCnt 개수를 (-L+1)개로 설정해줘야 한다
      --> 다음 블록 포함 L개는 경사로를 만들기 위해 사용되기 때문에 카운트하면 안됨! (핵심!!)
  • 큰 경우
    • 같은 값을 가리키는 preCnt가 L보다 크거나 같으면 경사로를 놓을 수 있음!

• 정리
  • prev가 다음 블록보다 작은 경우 preCnt = -L+1로 해주는 것이 핵심
    --> 다음 블록 포함 L개는 경사로를 만들기 위해 사용됨을 표기해야 하기 때문
  • vertical과 horizon은 기능은 같고 검사하는 위치만 다름