[BOJ_14890] 경사로 (java)

문제링크

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

14890번: 경사로

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 구현,사고

경사로 문제를 해결하기 위해서 경사로의 조건을 충분히 이해하고 구현해주어야 합니다.

출처 - https://www.acmicpc.net/problem/14890

위 경우는 경사로에 놓을 수 있는 경우들을 의미합니다. 문제에서 제시되는 경사로의 길이만큼 충분히 같은 수의 길이 있을 경우 경사로를 놓을 수 있으며 경사로를 놓을 때는 항상 1만 차이가 나야합니다.

출처 - https://www.acmicpc.net/problem/14890

위 경우는 경사로에 놓을 수 없는 경우입니다. 높이 차이가 2 이상인 경우 경사로를 놓을 수 없으며, 경사로를 겹쳐서 놓을 수 없습니다.

 

위 조건을 고려하여 &n*n& 배열에서 길을 찾아야합니다. 길이 시작하는 부분부터 앞으로 하나하나 나아가며 문제를 해결할 수 있습니다.

그 다음의 위치의 값이 같거나, 1 작거나, 1 크거나에 따라 구분하여 구현을 해주면 됩니다.

 

만약 같은 경우는 경사로를 놓을 길 한개가 추가 되었다고 생각해주면 됩니다.

 

만약 앞으로 나아간 길이 1 큰 경우 그동안 지나간 길을 보고 경사로를 놓을만큼 길이 충분히 긴지 확인하여줍니다.

 

만약 앞으로 나아간 길이 1이 작은 경우는 내려가는 경사로를 놓을 수 있는지 그 다음길들을 검사하여주면 됩니다.

 

구현코드

package backjoon_14890;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        int[][] map = new int[n][n];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                map[i][j] = sc.nextInt();
            }
        }

        int roadCount = 0;

        //가로 확인
        for(int i = 0; i < n; i++){
            int[] road = map[i];
            if(isRoad(road,l)) {
                roadCount += 1;
            }
        }

        //세로 확인
        for(int i = 0; i < n; i++){
            int[] road = new int[n];
            for(int j = 0; j < n; j++){
                road[j] = map[j][i];
            }
            if(isRoad(road,l)) {
                roadCount += 1;
            }
        }

        System.out.println(roadCount);
    }

    public static boolean isRoad(int[] road, int l){
        int equalCount = 1;
        int prev = road[0];
        int i = 1;
        for(;i< road.length; i++){
            if(road[i] == prev)
                equalCount++;
            else if(road[i] > prev && road[i]-1 == prev){
                if(equalCount < l)
                    break;
                prev = road[i];
                equalCount = 1;
            }
            else if(road[i] < prev && road[i]+1 == prev && i+l-1 < road.length){
                int j = 0;
                for(; j < l; j++){
                    if(road[i+j] != road[i])
                        break;
                }
                if(j != l)
                    break;
                i = i+l-1;
                prev = road[i];
                equalCount = 0;
            }
            else{
                break;
            }
        }
        return i == road.length;
    }
}

 

시간복잡도

길인지 한번 확인하는 방법은 2차원 배열중 한 줄만 확인하기 때문에 $O(n)$이 됩니다.

그리고 한줄짜리 배열이 총 $2n$개 있으므로  시간복잡도는 $O(n^2)이 됩니다.