[C++] 백준 BOJ 14890 경사로 (SWEA 4014 활주로 건설)

문제링크 : https://noj.am/14890

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH

<아래 풀이는 백준 14890 기준>

(이전 노드 - 현재 노드)의 높이 차이가 +1일 경우 : 내리막

(이전 노드 - 현재 노드)의 높이 차이가 -1일 경우 : 오르막

내리막 경사로가 건설되려면 앞으로 len 만큼의 길이가 확보되어야 하고

오르막 경사로가 건설되려면 이전에 이미 len 만큼의 길이가 확보되었어야 한다.

내리막 + 오르막 경사로가 건설되어야 할 경우에도 그 사이 길이가 len 만큼 확보되어야 한다.

공간의 확보를 위해선 높이의 차이가 같은 구간이 몇개인지 카운트를 해가면서 계산하면 된다.

// BOJ 14890 경사로
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int n, len;
    cin >> n >> len;
    vector<vector<int> > arr(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
 
    int result = 0;
    for (int i = 0; i < n; i++) {
        // 가로행
        int cnt = 1; // 높이가 같은 타일 수
        for (int j = 1; j < n; j++) {
            int prev = arr[i][j - 1];
            int cur = arr[i][j];
            // 높이가 같으면
            if (prev == cur)
                cnt++;
            // 내리막이면
            else if (prev - cur == 1 && cnt >= 0)
                cnt = -len + 1;
            // 오르막이면
            else if (prev - cur == -1 && cnt >= len)
                cnt = 1;
            else {
                cnt = -1;
                break;
            }
        }
        if (cnt >= 0)
            result++;
 
        // 세로행
        cnt = 1;
        for (int j = 1; j < n; j++) {
            int prev = arr[j - 1][i];
            int cur = arr[j][i];
            if (prev == cur)
                cnt++;
            else if (prev - cur == 1 && cnt >= 0)
                cnt = -len + 1;
            else if (prev - cur == -1 && cnt >= len)
                cnt = 1;
            else {
                cnt = -1;
                break;
            }
        }
        if (cnt >= 0)
            result++;
    }
    cout << result;
 
    return 0;
}

<SWEA 4014 소스코드>

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int tc;
    cin >> tc;
    for(int T = 1; T <= tc; T++) {
        int n, len;
        cin >> n >> len;
        vector<vector<int> > arr(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> arr[i][j];
 
        int result = 0;
        for (int i = 0; i < n; i++) {
            // 가로행
            int cnt = 1; // 높이가 같은 타일 수
            for (int j = 1; j < n; j++) {
                int prev = arr[i][j - 1];
                int cur = arr[i][j];
                // 높이가 같으면
                if (prev == cur)
                    cnt++;
                    // 내리막이면
                else if (prev - cur == 1 && cnt >= 0)
                    cnt = -len + 1;
                    // 오르막이면
                else if (prev - cur == -1 && cnt >= len)
                    cnt = 1;
                else {
                    cnt = -1;
                    break;
                }
            }
            if (cnt >= 0)
                result++;
 
            // 세로행
            cnt = 1;
            for (int j = 1; j < n; j++) {
                int prev = arr[j - 1][i];
                int cur = arr[j][i];
                if (prev == cur)
                    cnt++;
                else if (prev - cur == 1 && cnt >= 0)
                    cnt = -len + 1;
                else if (prev - cur == -1 && cnt >= len)
                    cnt = 1;
                else {
                    cnt = -1;
                    break;
                }
            }
            if (cnt >= 0)
                result++;
        }
        cout << "#" << T << " " << result << "\n";
    }
 
    return 0;
}