14890번) 경사로

.문제 출처 : https://www.acmicpc.net/problem/14890

기출 문제라네요.

import java.util.Scanner; public class Q14890 { static int num, L; static int[][] map; public static void main(String[] args) { Scanner sc = new Scanner(System.in); num = sc.nextInt(); map = new int[num][num]; L = sc.nextInt(); for ( int i = 0 ; i < num; i++ ) { for ( int j = 0; j < num; j++ ) { map[i][j] =  sc.nextInt(); } } int result = 0; for ( int i = 0 ; i < num; i++ ) { result += getPossible(i, true); result += getPossible(i, false); } System.out.println(result); } static int getPossible(int k, boolean vertical) { int start = 0, end = 0; for ( int i = 0; i < num-1; i++ ) { int now = map[k][i]; //default로 가로 이동 int next = map[k][i+1]; if ( vertical ) { //세로 이동 now = map[i][k]; next = map[i+1][k]; } if ( now > next ) { //내려간다. if ( i + L < num && now - 1 == next ) { //경사로 넣을 길이가 있고, 다음 땅이 한칸 내려가면 for ( int j = i + 2; j < i + L + 1; j++ ) { //경사로 길이 만큼 땅이 평평한지 확인 int moreNext = map[k][j]; if ( vertical ) { moreNext = map[j][k]; } if ( next != moreNext ) { //경사로 길이 만큼 땅이 평평하지 않으니 갈수 없다.(경사로 못넣음) return 0; } } start = i+L+1; end = i+L+1; continue; } return 0; } else if ( now < next ) { //올라간다. end = i; if ( end - start + 1 < L ) { //평평한 땅의 길이가 경사로보다 작으면 갈수 없다. return 0; } start = i + 1; } } return 1; } }

변수가 너무 많으면 코딩이 힘들기 때문에,

가로로 가는 방법만 생각하고, 경사로의 길이를 2로 정한 후 1차 코드를 짰습니다.

그 후 세로 방법에도 적용이 되는지 확인 후

경사로 길이를 동적으로 수정했습니다.

2018년 3월 11일 import java.util.Scanner; public class Q14890 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int mapSize = sc.nextInt(); int L = sc.nextInt(); int[][] map = new int[mapSize][mapSize]; for (int i = 0; i < mapSize; i++) { for (int j = 0; j < mapSize; j++) { map[i][j] = sc.nextInt(); } } solution(mapSize, L, map); } static void solution(int mapSize, int L, int[][] map) { int resultNum = 0; for (int i = 0; i < mapSize; i++) { //가로검색 int[] tempMap = map[i].clone(); resultNum += getRoute(mapSize, L, tempMap); //세로 검색 for (int j = 0; j < mapSize; j++) { tempMap[j] = map[j][i]; } resultNum += getRoute(mapSize, L, tempMap); } System.out.println(resultNum); } static int getRoute(int mapSize, int L, int[] searchMap) { int preHeight = searchMap[0]; int helperEndPosition = -1; //발판의 마지막 위치 for (int j = 1; j < mapSize; j++) { int nowHeight = searchMap[j]; if (preHeight == nowHeight) { //수평이다. -> 그냥 패스 continue; } else if (preHeight - 1 == nowHeight) { //내려간다. -> 이후 검사 int maxL = j + L - 1; if (maxL < mapSize) { //발판 사용 가능 여부 확인 for (int k = j + 1; k <= maxL; k++) { if (nowHeight != searchMap[k]) { return 0; } } helperEndPosition = maxL; j = maxL; preHeight = nowHeight; continue; } } else if (preHeight + 1 == nowHeight) { //올라간다. -> 이전 검사 int minL = j - L; if ( 0 <= minL && helperEndPosition < minL) { //발판 사용 가능 여부 확인 for (int k = minL; k < j; k++) { if (preHeight != searchMap[k]) { return 0; } } helperEndPosition = j - 1; preHeight = nowHeight; continue; } } return 0; } return 1; } }