[BOJ] 14890 경사로 - Java

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

14890번: 경사로

---

1. 문제

NxN 크기의 map에서 오르막길, 내리막길 경사로를 완전하게 놓아 지나갈 수 있는 길의 개수를 출력한다.

 

2. 풀이

이 문제는 놓치는 조건 없이 꼼꼼하게 봐야 하는 문제이다.

길을 지나갈 수 있는 경우는 3가지 이다.

1. 이전값과 현재값이 같은 경우

2. 이전값과 현재값이 1 차이 날 경우 => 경사면

   1) 현재값이 이전값보다 클 때(오르막길) - 같은거 L개를 지나왔을 경우

   2) 이전값이 현재값보다 클 때(내리막길) - 같은거 L개를 지날 수 있는 경우

이다.

 

여기서 주의해야할 점은 내리막길에서 같은거 L개를 지날 수 있을 때

- 좌표를 last 값 기준으로 맞춰줘야 하고(for문을 새로 돌게 되면 last는 map[i][j+L]이 된다.)

- 경사면을 아예 처음부터 다시 시작해야하므로 cnt는 1이 아니라 0으로 초기화해야 한다.

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int map1[][], map2[][], N, L, ans;
	static boolean isDown;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		map1 = new int[N][N];
		map2 = new int[N][N];
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				int num = Integer.parseInt(st.nextToken());
				map1[i][j] = num;
				map2[j][i] = num;
			}
		}
		// 입력 끝
		
		solution(map1);
		solution(map2);
		System.out.println(ans);
	}
	
	static void solution(int[][] map) {
		for (int i=0; i<N; i++) {
			int cnt = 1;
			boolean isOk = true;
			for (int j=0; j<N-1; j++) {
				int last = map[i][j];
				int now = map[i][j+1];
				int gap = Math.abs(now-last);
				
				if (gap == 0) {
					cnt++;
				} 
				else if (gap == 1) {
					if (now > last) { //오르막길
						if (cnt >= L) {
							cnt = 1;
							continue;
						}
						else {
							isOk = false;
							break;
						}
					}
					else if (now < last) {	//내리막길
						if (j+L >= N ) {
							isOk = false;
							break;
						}
						for (int k=1; k<=L; k++) {
							if (map[i][j+k] != now) {
								isOk = false;
								break;
							}
						}
						if (!isOk) break;
						cnt = 0;	//주의점1) 0인 이유 : 경사로 아예 처음부터 다시 시작해야 함
						j += L-1;	//주의점2) L-1인 이유 : j는 last 좌표로 맞춰야 함
					}
				} 
				else if (gap >= 2){
					isOk = false;
					break;
				}
			}
			if (isOk) {
				ans++;
			}
		}
	}
}

4. 사담

이틀 정도 걸렸으나 조건이 까다로워 블로그를 참고하였다. 분하다 꼭 다시 풀러와줄게..