[백준 14890] 경사로 (C++)

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

14890번: 경사로

골드3 문제지만 생각만 잘 하면 30분이면 해결가능하다.

시간도 2초로 매우 넉넉하다..

코드는 매우 간단하다.

row와 col를 벡터로 선언하여 전달한다. 각 downhill이 가능한지 check하기 위해 복사하여 넘기는 방식으로 하였다.
Downhill_Discrimination 함수에서는 다음과 같은 과정으로 경사로가 가능한지 check한다.

bool check[100]을 선언한다.
L=2일때 앞뒤로 경사로가 겹치는 경우, 즉 내려갔다 올라가는 경우 평지가 4가 필요한데 , 4보다 적은 것을 check하기 위한것이다. 

이때 내려가는 부분먼저 check한다. 높이가 2이상 차이나면 return;

line[i] - line[i+1]이 1, 즉 내려가는 방향이면 둘 수 있는지 확인한다.
확인 방식은 L개만큼 연속된 평지가 있어야 하므로 첫번째 IF문은 조건이 i+count < N 이다. index안에서만 해결
그 다음은 평지인지와 check[i+count]가 false인지 check한다.
지금 생각하니 내리막에서는 딱히 check를 할 필요가 없을거 가다.

 

오르막은 똑같다, 이것은 N-1부터 1까지 check한다.
논리는 모두 같다. 

전체코드는 다음과 같다.

// 경사로
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct check_hill {
    int index;
    int up_down; // -1 이면 올라가는 방향 , 1 이면 내려가는 방향, 0 
};
int N, L;
int MAP[100][100];
int count_res = 0;
void Downhill_Discrimination(vector<int>& line) {
    // 경우의 수
    // 우선 높이 차이가 2이면 return
    bool check[100] = { false };
    // 내려가는거 체크
    for (int i = 0; i < N - 1; i++) {
        if (abs(line[i] - line[i + 1]) >= 2)
            return;
        if (line[i] - line[i + 1] == 1) { // 내려 가는 방향이면
            int level = line[i + 1];
            for (int count = 1; count <= L; count++) {
                if (i + count < N) {
                    if (level == line[i + count] && check[i+count] == false) {
                        check[i+count] = true;
                    }
                    else {
                        return;
                    }
                }
                else {
                    return;
                }
            }
        }
    }
    // 올라가는거 체크
    for (int i = N - 1; i > 0; i--) {
        if (abs(line[i] - line[i - 1]) >= 2)
            return;
        if (line[i] - line[i - 1] == 1) {
            int level = line[i - 1];
            for (int count = 1; count <= L; count++) {
                if (i - count > -1) {
                    if (level == line[i - count] && check[i - count] == false) {
                        check[i - count] = true;
                    }
                    else {
                        return;
                    }
                }
                else {
                    return;
                }
            }
        }
    }
    count_res++;
}
void solve() {
    // 행열 처리
    for (int i = 0; i < N; i++) {
        vector<int> row;
        vector<int> col;
        for (int j = 0; j < N; j++) {
            row.push_back(MAP[i][j]);
            col.push_back(MAP[j][i]);
        }
        Downhill_Discrimination(row);
        Downhill_Discrimination(col);
    }
    cout << count_res << endl;
}
void input() {
    cin >> N >> L;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> MAP[i][j];
}
void init() {
    cin.tie(0)->sync_with_stdio(false);
}
int main() {
    init();
    input();
    solve();
}