백준 14890번 경사로 풀이

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

백준 14890번 문제 경사로 풀이이다.

구현 문제인데, 어떻게 하면 효율적으로 풀 지 고민을 해 보았다.

만약 경사로가 다음과 같이 나타난다면 다음과 같은 자료구조로 변환하여 문제를 풀이하였다.

1 1 1 1 2 2 3 3 3 3 3

만약 위와 같은 형태로 경사로가 구성되어 있다면, 1이 4개 2가 2개 3이 5개이므로 다음과 같은 형태로 저장한다.

(1, 4) (2, 2) (3, 5)

경사로를 놓는데에 L의 길이가 필요하다면, 낮은 위치에 길이를 L만큼 제외하고 음수가 되게 되면 실패한다고 생각하였다.

 

#include <bits/stdc++.h>
using namespace std;

int field[105][105];
int road[105];
typedef pair<int, int> pii;
int main() {
    int n;
    int l;
    cin >> n >> l;
    int ans = 0;
    for (int i=1; i <= n; i++) {
        for (int j=1;j <= n; j++) {
            cin >> field[i][j];
        }
    }
    
    //garo check
    vector<pii> arr; //값, 연속개수
    for (int i=1; i <= n; i++) {
        arr.clear();
        int prev = field[i][1];
        int prev_num = 1;
        for (int j=2; j <= n ;j++) {
            auto& cur = field[i][j];
            if (cur != prev) {
                arr.push_back(make_pair(prev, prev_num));
                prev_num = 0;
            }
            prev_num++;
            prev = cur;
        }
        arr.push_back(make_pair(prev, prev_num));

        bool correct = true;
        for (int k=1; k < (int)arr.size(); k++) {
            auto& p_height = arr[k-1].first;
            auto& p_length = arr[k-1].second;
            auto& c_height = arr[k].first;
            auto& c_length = arr[k].second;
            int delta = p_height - c_height;
            if (delta*delta > 1) {
                correct = false;
                break;
            }
            if (p_height == c_height+1) {
                c_length -= l;
                if (c_length < 0) {
                    correct = false;
                }
            } else if (p_height+1 == c_height) {
                p_length -= l;
                if (p_length < 0) {
                    correct = false;
                }
            }
        }
        
        if (correct) {
            ans++;
        }
    }
    
    //sero check
    for (int i=1; i <= n; i++) {
        arr.clear();
        int prev = field[1][i];
        int prev_num = 1;
        for (int j=2; j <= n ;j++) {
            auto& cur = field[j][i];
            if (cur != prev) {
                arr.push_back(make_pair(prev, prev_num));
                prev_num = 0;
            }
            prev_num++;
            prev = cur;
        }
        arr.push_back(make_pair(prev, prev_num));

        bool correct = true;
        for (int k=1; k < (int)arr.size(); k++) {
            auto& p_height = arr[k-1].first;
            auto& p_length = arr[k-1].second;
            auto& c_height = arr[k].first;
            auto& c_length = arr[k].second;
            int delta = p_height - c_height;
            if (delta*delta > 1) {
                correct = false;
                break;
            }
            if (p_height == c_height+1) {
                c_length -= l;
                if (c_length < 0) {
                    correct = false;
                }
            } else if (p_height+1 == c_height) {
                p_length -= l;
                if (p_length < 0) {
                    correct = false;
                }
            }
        }
        
        if (correct) {
            ans++;
        }
    }
    
    cout << ans << endl;
    
	return 0;
}