백준 14890 경사로 (C++)

안유태·2022년 7월 22일
0

알고리즘

목록 보기
12/239

14890번: 경사로

문제에서 제시해준 조건들에 맞춰 구현을 해주면 되는 문제이다. 조건은 4가지로 분류했다.

1. 다음 칸의 높이가 동일할 때
2. 다음 칸의 높이가 1만큼 높을 때
3. 다음 칸의 높이가 1만큼 낮을 때
4. 그 외의 경우

먼저 배열을 입력받을 때 map2에 행열을 뒤집어서 저장해두었다. 그 후 반복문을 돌면서 길을 찾게 되는데 앞서 설명한 조건문들을 구현하였다. same_road를 이용하여 지나온 동일한 높이의 칸 수를 저장하여 1만큼 높을 때 가능한지 확인하였고, 1만큼 낮을 때 여부를 확인하기 위해 뒤 칸들이 L만큼 연속하여 동일한 높이의 칸들이 있는지 확인하였다.
문제에 제시된 조건들만 잘 구현하면 되는 문제였지만 생각하는데 좀 머리가 아픈 문제였다. 행열을 뒤집는 기술도 잘 기억해둬야겠다.



#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, L, res = 0;
int map1[101][101];
int map2[101][101];

void findRes(int A[101][101]) {
    for (int i = 0; i < N; i++) {
        int tf = true;
        int same_road = 1;

        for (int j = 0; j < N - 1; j++) {
            // 같을 때
            if (A[i][j] == A[i][j + 1]) same_road++;
            // 한칸 높을 때
            else if (A[i][j] + 1 == A[i][j + 1]) {
                if (same_road >= L) {
                    same_road = 1;
                }
                else {
                    tf = false;
                    break;
                }
            }
            // 한칸 낮을 때
            else if (A[i][j] == A[i][j + 1] + 1) {
                int tf2 = true;
                for (int k = j + 1; k < j + 1 + L; k++) {
                    if (A[i][j + 1] != A[i][k]) tf2 = false;
                }
                if (tf2) {
                    j = j + L - 1;
                    same_road = 0;
                }
                else {
                    tf = false;
                    break;
                }
            }
            else {
                tf = false;
                break;
            }
        }

        if (tf) res++;
    }
}

void solution() {
    findRes(map1);
    findRes(map2);

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> L;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map1[i][j];
            map2[j][i] = map1[i][j];
        }
    }

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글