BOJ 14890 : 경사로

문제링크

풀이요약

구현

풀이상세

1. 주어진 문제에 맞춰 차례대로 구현한다. 내가 중요하게 본 점은 총 3개이다.
   • 다음 값 대비 1 만큼 높아진 경우
   • 다음 값 대비 1 만큼 낮아진 경우
   • 다음 값 대비 2 이상 혹은 이하로 낮아진 경우
2. 1만큼 높거나 낮은 경우에는 각 L 만큼의 범위를 확인하여, 배열의 범위안에 속하며, 범위의 모든 수가 같고, 이전 탐색에서 경사로를 놓지 않았다면 현재 인덱스 범위만큼 경사로를 놓을 수가 있다.
3. 경사로를 놓을 수 있다는 것이 확인되었다면 범위만큼 미리 방문처리를 하자.

배운점

• 구현문제에서 최적해나 묘수가 보이지 않는다면 그냥 생각하지 말고 푸는게 코테에 더 도움이 될 거 같다.

#include <iostream>
#include <string.h>
using namespace std;
int N, L, ans;
int ar[101][101], ac[101][101];
int visited[101];
string s;
void input() {
    cin >> N >> L;
    for (int i = 0; i < N; i++) {
        s = "";
        for (int j = 0; j < N; j++) {
            cin >> ac[i][j];
            ar[j][i] = ac[i][j];
        }
    }

}

void solve(int a[101][101]) {
    for (int i = 0; i < N; i++) {
        bool check = true;
        memset(visited, 0, sizeof(visited));
        for (int j = 0; j < N - 1; j++) {
            if (a[i][j] == a[i][j + 1] + 1) {
                int curr = a[i][j + 1];
                for (int k = j + 1; k <= j + L; k++) {
                    if (k >= N || a[i][k] != curr || visited[k]) {
                        check = false;
                        break;
                    }
                }
                if (check) {
                    for (int k = j + 1; k <= j + L; k++) visited[k] = 1;
                }
            } else if (a[i][j] == a[i][j + 1] - 1) {
                int curr = a[i][j];
                for (int k = j - L + 1; k <= j; k++) {
                    if (k < 0 || a[i][k] != curr || visited[k]) {
                        check = false;
                        break;
                    }
                }
                if (check) {
                    for (int k = j - L + 1; k <= j; k++) visited[k] = 1;
                }
            } else if (a[i][j] - a[i][j + 1] < -1 || a[i][j] - a[i][j + 1] > 1) {
                check = false;
                break;
            }
        }
        if (check) {
            ans++;
        }
    }
}

void output() {
    cout << ans;
}

int main() {
    input();
    solve(ac);
    solve(ar);
    output();
}