[백준 14890번] 경사로

문제 링크: 14890번 경사로

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

 

꼼꼼함이 요구되는 문제였다. 물론 처음부터 모든 경우의 수를 고려하는 것도 중요하겠지만, 현실적으로 스스로를 완전히 신뢰할 수는 없기에 많은 엣지 케이스를 테스트해보는 것도 좋은 방법일 것이다.

일단 가로든 세로든 각 길에 대해서 한 방향으로만 경사로를 놓을 수 있는지 체크하면 된다. 즉 예를 들어서 가로 길의 경우, 왼쪽에서 오른쪽으로 이동하면서 경사로를 놓을 수 있다면 오른쪽에서 왼쪽은 체크할 필요가 없다.

이 문제의 경우에는 다음과 같은 경우를 체크하는 것이 까다로웠다.

 

 

이를 위해서 내리막이 있을 때 먼저 내리막 이후의 평지에 대해서 시작 인덱스와 끝 인덱스를 구하고, 끝 인덱스 이후의 땅이 1만큼 높은지 확인한다. 이러한 조건에서 해당 평지의 길이가 경사로 길이의 2배보다 짧으면 내려가는 경사로와 올라가는 경사로 2개를 모두 놓을 수 없는 것이기에 false를 반환한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int[][] map;
    static int n;
    static int l; // 경사로 길이

    static boolean check(int[] arr) {
        int posPlainStart = 0;

        for (int i = 1; i < n; i++) {
            int diff = arr[i] - arr[i-1]; // 높이 차이

            if (diff == 0)
                continue;

            if (Math.abs(diff) > 1)
                return false;

            if (diff == 1) {
                if (i - posPlainStart < l)
                    return false;
                posPlainStart = i;
                continue;
            }

            // if diff == -1
            // i: 한 칸 낮은 땅의 시작 좌표, j: 한 칸 낮은 땅의 끝 좌표
            int j = i;
            while (j < n-1 && arr[j+1]==arr[j])
                j++;

            // 경사로를 놓을 자리가 없을 때
            if (j-i+1 < l)
                return false;

            // 올라가는 경사로도 놓아야 할 때
            if (j<n-1 && arr[j+1]==arr[j]+1 && j-i+1 < l*2)
                return false;
        }

        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] temp;
        temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = temp[0];
        l = temp[1];

        map = new int[n][n];
        for (int i = 0; i < n; i++)
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int answer = 0;
        int[] t = new int[n];

        // 가로 길
        for (int i = 0; i < n; i++)
            if (check(map[i]))
                answer++;

        // 세로 길
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                t[j] = map[j][i];
            if (check(t))
                answer++;
        }

        System.out.println(answer);
    }
}