14890번 경사로

삼성 SW 역량 테스트 기출문제이다.

어려웠었다.

나는 행과 열도 서로 겹치는 부분을 어떻게 생각해야할지 몰라서 다른 분의 코드를 보았다.

그런데, 정답 코드들도 보니, 행과 열은 서로 안 겹쳐도 되는 것 같다.

행과 열을 나누어서 생각하면 된다.

https://www.acmicpc.net/problem/14890

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int map[101][101] = { 0, };
 
int N = 0, L = 0;
 
int check_row(int row)
{
    int ret = 0;
 
    if (row == N) return ret;
 
    bool check = true;
 
    int length = 1;
 
    for (int column = 0; column < N - 1; column++)
    {
        if (map[row][column] == map[row][column + 1])
        {
            ++length;
 
            continue;
        }
 
        if (map[row][column + 1] - map[row][column] == 1)
        {
            if (length >= L)
            {
                length = 1;        
            }
            else
            {
                check = false;
 
                break;
            }    
 
            continue;
        }
 
        if (map[row][column] - map[row][column + 1] == 1)
        {
            if (column + L >= N)
            {
                check = false;
 
                break;
            }
 
            for (int len = 1; len <= L; len++)
            {
                if (map[row][column + 1] != map[row][column + len])
                {
                    check = false;
 
                    break;
                }
            }
 
            if (!check) break;
 
            length = 0;
 
            column = column + L - 1;
 
            continue;
        }
 
        check = false;     
        // 2 이상 차이나는 경우는 위의 if문들에서 걸리는 것이 없고, 여기에서 걸리므로, 바로 false
 
        break;
    }
 
    if (check) ++ret;
 
    ret += check_row(row + 1);
 
    return ret;
}
 
int check_column(int column)
{
    int ret = 0;
 
    if (column >= N) return ret;
 
    bool check = true;
 
    int length = 1;
 
    for (int row = 0; row < N - 1; row++)
    {
        if (map[row][column] == map[row + 1][column])
        {
            ++length;
 
            continue;
        }
 
        if (map[row + 1][column] - map[row][column] == 1)
        {
            if (length >= L)
            {
                length = 1;            
            }
            else
            {
                check = false;
 
                break;
            }
 
            continue;
        }
 
        if (map[row][column] - map[row + 1][column] == 1)
        {
            if (row + L >= N)
            {
                check = false;
 
                break;
            }
 
            for (int len = 1; len <= L; len++)
            {
                if (map[row + len][column] != map[row + 1][column])
                {
                    check = false;
 
                    break;
                }
            }
 
            if (!check) break;
 
            length = 0;
 
            row = row + L - 1;
 
            continue;
        }
 
        check = false;
        // 2 이상 차이나는 경우는 위의 if문들에서 걸리는 것이 없고, 여기에서 걸리므로, 바로 false
 
        break;
    }
 
    if (check) ++ret;
 
    ret += check_column(column + 1);
 
    return ret;
}
 
int main(void)
{
    int result = 0;
 
    scanf("%d %d", &N, &L);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
 
    result = check_row(0) + check_column(0);
 
    printf("%d\n", result);
    
    return 0;
}