2 분 소요

문제

문제 바로가기

입력

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

접근방법

img

문제의 나온 조건 중에 위의 그림을 잘 이해하고 주의해야한다.

높은 곳에서 낮은 곳으로 내려가는 부분을 신경써서 문제를 풀었다.

  • 가로방향과 세로방향을 분리해서 함수를 작성했다. 따라서 동일한 방법을 2번 반복했다.
  • 우선 높이의 차이가 2 이상인 부분이 나오면 그 줄은 신경을 안써도 된다.
  • 동일한 높이의 수가 연속해서 나올 때는 count에 개수를 저장해주었다.
  • 직전에 내리막길을 만나면 down을 true로 만들고, 오르막길을 만날 땐 false로 만들어서 구별을 해주었다.
  • 내리막길을 만날 때 down이 false이면 count를 초기화하고 계속 진행해주면 되고, down이 true이면 count가 L보다 같거나 클 때 진행을 해주었다.
  • 오르막길을 만나면 count와 L을 비교해서 count가 같거나 더 크면 진행을 해주었고, 만약에 down이 true로 되어있으면 내리막길을 위한 사다리도 만들어야되기 때문에 count가 2*L 보다 같거나 커야 한다.
  • 마지막에 함수 안에서 반복문을 모두 마쳤을 때, down이 true일 때를 고려해야 한다. 따라서 true이면, 동일한 방법으로 count와 L을 비교해주었다.

풀이

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

public class Main {
    static int N, L;
    static int[][] map;
    static int cnt = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        map = new int[N][N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < N; i++) {
            routeX(i);
            routeY(i);
        }

        System.out.println(cnt);
    }

    public static void routeX(int x) {
        int count = 1;
        boolean down = false;
        for(int i = 1; i < N; i++) {
            if(Math.abs(map[x][i-1] - map[x][i]) > 1) {
                return;
            }
            else if(map[x][i-1] > map[x][i]) {
                if(down && count < L)
                    return;
                down = true;
                count = 1;
            }
            else if(map[x][i-1] < map[x][i]) {
                if(down) {
                    count -= L;
                }
                if(count < L) {
                    return;
                }
                else {
                    down = false;
                    count = 1;
                }
            }
            else
                count++;
        }

        if(down && count < L) {
            return;
        }
        cnt++;
    }

    public static void routeY(int y) {
        int count = 1;
        boolean down = false;
        for(int i = 1; i < N; i++) {
            if(Math.abs(map[i-1][y] - map[i][y]) > 1) {
                return;
            }
            else if(map[i-1][y] > map[i][y]) {
                if(down && count < L)
                    return;
                down = true;
                count = 1;
            }
            else if(map[i-1][y] < map[i][y]) {
                if(down) {
                    count -= L;
                }
                if(count < L) {
                    return;
                }
                else {
                    down = false;
                    count = 1;
                }
            }
            else
                count++;
        }

        if(down && count < L) {
            return;
        }
        cnt++;
    }
}

댓글남기기

참고