[Algorithm] 백준 14890번 경사로

백준 14890번 경사로

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

문제 풀이

- 경사로 조건

  1. 경사로는 낮은 칸에 놓으며, L개의 연속된 칸의 높이가 동일해야함.

  2. 낮은 칸과 높은 칸의 차이는 오직 1이어야 함.

- 경사로를 놓는 2가지 경우

  1. 이전 칸이 현재 칸보다 1 낮은 경우 (이전 칸 높이 < 현재 칸 높이)

      - 첫 번째부터 순차적으로 보기 때문에, 이러한 상황을 마주칠 때까지 counting해서 처리.

      - 높이가 낮은 칸에 경사로를 놓기 때문에, 현재 칸은 사용할 수 있어서 count 1로 시작 (Line 21, 50)

  2. 이전 칸이 현재 칸보다 1 큰 경우 (이전 칸 높이 > 현재 칸 높이)

      - 현재 칸에서 뒤의 칸까지 총 L개가 높이가 동일한지 확인해야함. (Line 24~31, 53~60)

      ※ 주의사항 ※

      1. 경사로는 맵을 넘어가서는 안됨.

          → L개의 높이를 확인하기 전 체크해줘야 함.

      2. 이미 경사로가 놓인 자리에 경사로를 놓을 수 없음.  

          → 사용할 수 없는 칸이므로 counting을 초기화해줘야 함. (Line 25, 54)

P.S.

문제에 다양한 조건이 걸려있는 경우는 조건을 잘 정리해서 시작하는 것이 중요함.

무턱대고 시작했을 때, 로직이 벗어날 확률이 높음. 

이럴 때는 그냥 코드 지우고 새로 짭시다. !!!!!!!!!!!!!!!!!!!!!!

그러지 않고, 로직이 벗어난 상태에서 하나씩 추가해서 수정하면, 개망할 확률 92%.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
 
using namespace std;
int N, L;
int map[101][101];
 
// 세로로 횡단
int solveVertical(int col) {
    int shCnt = 1;
    for (int i = 1; i < N; i++) {
        int gap = map[i][col] - map[i - 1][col];
        if (abs(gap) >= 2) {
            return 0;
        }
        else if (gap == 1) {
            if (shCnt < L) return 0;
            else {
                shCnt = 1;
            }
        }
        else if (gap == -1) {
            shCnt = 0;
            if (i + L > N) return 0;
            for (int j = i + 1; j < i + L; j++) {
                if (map[i][col] != map[j][col]) return 0;
            }
            i += (L - 1);
        }
        else {
            shCnt++;
        }
    }
    return 1;
}
 
// 가로로 횡단
int solveHorizontal(int row) {
    int shCnt = 1;
    for (int i = 1; i < N; i++) {
        int gap = map[row][i] - map[row][i - 1];
        if (abs(gap) >= 2) {
            return 0;
        }
        else if (gap == 1) {
            if (shCnt < L) return 0;
            else {
                shCnt = 1;
            }
        }
        else if (gap == -1) {
            shCnt = 0;
            if (i + L > N) return 0;
            for (int j = i + 1; j < i + L; j++) {
                if (map[row][i] != map[row][j]) return 0;
            }
            i += (L - 1);
        }
        else {
            shCnt++;
        }
    }
    return 1;
}
int main()
{
    int answer = 0;
    cin >> N >> L;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        answer += solveHorizontal(i);
        answer += solveVertical(i);
    }
    cout << answer;
    system("pause");
    return 0;
}