문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH

코드 (Java)

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

class Solution
{
	public static void main(String args[]) throws Exception
	{
//		System.setIn(new FileInputStream("res/input.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;
		T=Integer.parseInt(br.readLine().trim());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine().trim());
			int N = Integer.parseInt(st.nextToken());
			int X = Integer.parseInt(st.nextToken());
			int cnt = 0;
			
			int[][] field = new int[N][N];
			for (int row = 0; row < N; ++row) {
				st = new StringTokenizer(br.readLine().trim());
				for (int col = 0; col < N; ++col) {
					field[row][col] = Integer.parseInt(st.nextToken());
				}
			}
			
			// check according to row
			for (int row = 0; row < N; ++row) {
				int curHeight = field[row][0];
				int sameHeightCnt = 1;
				boolean possible = true;
				
				for (int col = 1; col < N; ++col) {
					int nextHeight = field[row][col];
					if (nextHeight < curHeight) {
						//it gets lower.
						if (curHeight - nextHeight > 1) {
							//too high.
							possible = false;
							break;
						}
						if (sameHeightCnt < 0) {
							//not enough roads
							possible = false;
							break;
						}
						sameHeightCnt = 1 - X;
						curHeight = nextHeight;
						
					} else if (nextHeight > curHeight) {
						//it gets higher
						//we need to see if we can add a slope WHILE considering before status.
						//But it'll be done automatically
						if (nextHeight - curHeight > 1) {
							//too high.
							possible = false;
							break;
						}
						if (sameHeightCnt < X) {
							//not enough roads
							possible = false;
							break;
						}
						sameHeightCnt = 1;
						curHeight = nextHeight;
					} else {
						sameHeightCnt++;
					}
				}
				
				if (possible && sameHeightCnt >= 0) ++cnt;
//				System.out.printf("row %d rowwise possible? : %b with %d cnt\n", row, possible, sameHeightCnt);
			}
			
			// check according to column
			for (int col = 0; col < N; ++col) {
				int curHeight = field[0][col];
				int sameHeightCnt = 1;
				boolean possible = true;
				
				for (int row = 1; row < N; ++row) {
					int nextHeight = field[row][col];
					if (nextHeight < curHeight) {
						if (curHeight - nextHeight > 1) {
							//too high.
							possible = false;
							break;
						}
						if (sameHeightCnt < 0) {
							//not enough roads
							possible = false;
							break;
						}
						sameHeightCnt = 1 - X;
						curHeight = nextHeight;
						
					} else if (nextHeight > curHeight) {
						//it gets higher
						//we need to see if we can add a slope WHILE considering before status.
						//But it'll be done automatically
						if (nextHeight - curHeight > 1) {
							//too high.
							possible = false;
							break;
						}
						if (sameHeightCnt < X) {
							//not enough roads
							possible = false;
							break;
						}
						sameHeightCnt = 1;
						curHeight = nextHeight;
					} else {
						sameHeightCnt++;
					}
				}
				
				if (possible && sameHeightCnt >= 0) ++cnt;
//				System.out.printf("col %d columnwise possible? : %b with %d cnt\n", col, possible, sameHeightCnt);
			}
			
			bw.write("#" + test_case + " " + cnt + "\n");
			bw.flush();

		}
//		bw.flush();
		bw.close();
	}
}

풀이

• 구현 + 브루트포스

• 테스트 케이스 개수랑 최대 크기가 작아서 일일이 다 확인해봐도 상관 없다.

• sameHeightCnt를 기준으로 경사로 배치 가능 여부를 파악하는데, 낮아지는 경우 이전의 높았던 높이에 대한 경사로를 채울 수 있는지 확인하기 위해 sameHeightCnt를 음수로 둔다. 이 조건을 활용해가지고 매 높이 변동때마다 이전 경사로/다음 경사로 배치 가능 여부를 확인하면 된다. 또 끝까지 도달했을 경우 이전에 내려간 상황 때문에 경사로를 배치해야 하는 상황인지 또 확인하기 위해 sameHeightCnt를 재차 확인한다.