[algorithm] 백준 - 경사로

삼성 SW 기출문제이다.

구현문제인데, 문제를 이해하고 나면 쉽게 풀 수 있는 문제이다.

 

문제를 분석해보면, 탐색할 때 총 세가지의 경우로 나눌 수 있다.

이 외의 경우는 탐색에서 나가도록 break 처리 해준다.

1. 현재 칸과 같은 높이의 칸일 때

 

길이가 L인 경사로를 놓기 위해서는 동일한 칸의 개수를 세야한다.

그러므로 현재 칸과 같은 높이의 칸일 때 칸의 개수를 증가해준다.

 

2. 현재 칸보다 한칸 높은 층일 때

 

칸의 개수가 L보다 작을 때 경사로를 놓을 수 없으니까 탐색에서 나가도록 break 처리한다.

그렇지 않으면 칸의 개수를 1로 갱신한다.

현재 칸을 고려하여 0이 아닌 1로 갱신해야한다.

 

3. 현재 칸보다 한칸 낮은 층일 때

 

칸의 개수가 이미 음수일 경우엔 탐색에서 나가도록 break처리한다.

그렇지 않은 경우, 앞으로 한칸 낮은 층의 개수가 l을 채워야 하므로 칸의 개수를 -L + 1로 설정한다.

 

마지막으로 답을 체크할 땐, 칸의 개수가 양수거나 0인 경우만 답으로 처리한다.

 

코드로 구현했을 때, 이렇다.

//경사로
#include <iostream>
using namespace std;

int main(void){
    int n, l, answer = 0;
    cin >> n >> l;
    int vertex[100][100];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> vertex[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        pair<int,int> node = {vertex[i][0], 0};
        for(int j = 0; j < n; j++){
            if(node.first == vertex[i][j] || node.first + 1 == vertex[i][j] || node.first - 1 == vertex[i][j]){
                //1번 경우
                if(node.first == vertex[i][j]){
                    node.second++;
                }
                // 2번 경우
                if(node.first - 1 == vertex[i][j]){
                    if(node.second < 0) break;
                    node.first = vertex[i][j];
                    node.second = -l + 1;
                }
                // 3번 경우
                if(node.first + 1 == vertex[i][j]){
                    if(node.second < l) break;
                    node.first = vertex[i][j];
                    node.second = 1;
                }
                // 마지막에서 답체크
                if(j == n - 1 && node.second >= 0){
                    answer++;
                }
            }
            else{
                break;
            }
        }
    }
    for(int i = 0; i < n; i++){
        pair<int,int> node = {vertex[0][i], 0};
        for(int j = 0; j < n; j++){
            if(node.first == vertex[j][i] || node.first + 1 == vertex[j][i] || node.first - 1 == vertex[j][i]){
                if(node.first == vertex[j][i]){
                    node.second++;
                }
                if(node.first - 1 == vertex[j][i]){
                    if(node.second < 0) break;
                    node.first = vertex[j][i];
                    node.second = -l + 1;
                }
                if(node.first + 1 == vertex[j][i]){
                    if(node.second < l) break;
                    node.first = vertex[j][i];
                    node.second = 1;
                }
                if(j == n - 1 && node.second >= 0){
                    answer++;
                }
            }
            else{
                break;
            }
        }
    }
    cout << answer;
}