14890번

14890번 - 경사로

저번 하반기에 SW역량평가에서 나왔던 문제이다.. 그때도 결국 예제는 다 맞았는데, 집와서 생각해보니 실수한 부분이 있었다.

시뮬레이션 문제이기 떄문에, 생각하고 푸는게 중요한 것 같다.

다시 풀어보는데, 충분히 생각을 먼저하고 풀지 않아서, 의식의 흐름대로 풀다보니 디버그에서도 뭐가 뭔지 헷갈렸다.

나는 재귀함수를 이용해서 왼쪽에서 오른쪽으로 검사하는 countPath1, 위에서 아래로 검사하는 countPath2 를 구현했다.

두 함수는 배열의 인덱스 값만 뒤바꿔주면 사실은 같은 함수가 된다.

로직은 다음칸이 나랑 같으면 같은 칸이 몇칸 축적됐는지 알려주는 c값을 저장했다. ( 단 처음에 1로 초기화)

그리고 경사로를 설치하기 위해서는 결국 1칸이 높던지, 1칸이 낮아야 하므로 그에 따라 if문을 설정했다.

만약 다음칸이 높은 경우에는, 지금까지 축적된 칸(c값)이 주어진 경사로 길이 l 보다 크거나 같아야 한다. 그리고 c를 1로 초기화 한다.

다음칸은 결국 새로 시작하는 것과 똑같기 때문에,

하지만 다음칸이 낮은 경우에는, l칸까지의 칸의 크기가 모두 같아야함을 for문을 하나 더 만들어서 체크한다.

그리고 c=0으로 만들고, 경사로 끝 칸부터 다시 탐색을 시작한다. 이 부분을 캐치해내니까 문제를 금방 풀 수 있었다.

충분히 생각을 하고 문제를 푸는게 오히려 시간을 더 줄일 수 있다는 사실을 잊지 말아야 겠다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
int n, l, ans;
vector<vector<int>> map;
int countPath1(int k)
{
    int ret = 0;
    
    if (k == n)
    {
        return ret;
    }
 
    bool chk = true;
    int c = 1;
    for (int i = 0; i < n-1; i++)
    {
        if (map[k][i] == map[k][i + 1])
        {
            c++;
            continue;
        }
 
        if (map[k][i + 1] - map[k][i] == 1)
        {
            if (c >= l)
            {
                c = 1;
            }
            else
            {
                chk = false;
                break;
            }
 
            continue;
        }
 
        if (map[k][i] - map[k][i + 1] == 1)
        {
            if (i + l >= n)
            {
                chk = false;
                break;
            }
 
            for (int t = 1; t <= l; t++)
            {
                if (map[k][i + t] != map[k][i + 1])
                {
                    chk = false;
                    break;
                }
            }
 
            if (!chk)
            {
                break;
            }
 
            c = 0;
            i = i + l - 1;
 
            continue;
        }
 
        chk = false;
        break;
    }
    
    if (chk)
    {
        ret += 1;
    }
 
    ret += countPath1(k + 1);
 
    return ret;
}
int countPath2(int k)
{
    int ret = 0;
 
    if (k == n)
    {
        return ret;
    }
 
    bool chk = true;
    int c = 1;
    for (int i = 0; i < n - 1; i++)
    {
        if (map[i][k] == map[i+1][k])
        {
            c++;
            continue;
        }
 
        if (map[i+1][k] - map[i][k] == 1)
        {
            if (c >= l)
            {
                c = 1;
            }
            else
            {
                chk = false;
                break;
            }
 
            continue;
        }
 
        if (map[i][k] - map[i+1][k] == 1)
        {
            if (i + l >= n)
            {
                chk = false;
                break;
            }
 
 
            for (int t = 1; t <= l; t++)
            {
                if (map[i+t][k] != map[i+1][k])
                {
                    chk = false;
                    break;
                }
            }
 
            if (!chk)
            {
                break;
            }
 
            c = 0;
            i = i + l - 1;
 
            continue;
        }
 
        chk = false;
        break;
    }
 
    if (chk)
    {
        ret += 1;
    }
 
    ret += countPath2(k + 1);
 
    return ret;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n >> l;
    map.assign(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
        }
    }
 
 
    ans+=countPath1(0)+ countPath2(0);
 
    cout << ans << "\n";
    
    return 0;    
}