(백준) 14890번 - 경사로

문제

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

풀이

배열을 행, 열 방향으로 순회하며 경사로를 설치한다.

지난 평지의 개수를 cnt에 저장했고, 내리막 경사로 설치 여부를 저장하는 down 변수를 사용했다.

• 다음 길의 높이가 같으면 cnt를 증가시킨다.
• 다음 길의 높이가 1만큼 큰 경우 cnt가 경사로 길이보다 작으면 설치할 수 없다.
• 다음 길의 높이가 1만큼 낮은 경우 이전 내리막 경사로를 설치하지 못한 경우 현재 내리막 경사로 또한 설치할 수 없다.
• 다음 길과의 높이 차가 2 이상이면 경사로를 설치할 수 없다.
• 내리막 경사로를 설치하고 cnt, down 변수를 적절하게 초기화해야 한다.
• 순회를 마쳤으나 내리막 경사로를 설치하지 못한 경우 불가능한 경우이다.

코드

#include <iostream>

using namespace std;

int board[101][101];

int main() {
	int n, l;
	cin >> n >> l;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}

	int ans = 0;

	// 행 확인
	for (int i = 0; i < n; i++) {
		int cnt = 1; // 높이가 같은 길의 수
		bool down = false; // 내리막 경사로 설치해야하는지
		bool failed = false;
		for (int j = 0; j < n - 1; j++) {
			// 내리막 경사로 설치 후 초기화
			if (down && cnt >= l) {
				cnt = 0;
				down = false;
			}

			if (board[i][j] == board[i][j + 1]) {
				cnt++;
			}
			// 다음 길이 높은 경우
			else if (board[i][j] - board[i][j + 1] == -1) {
				if (cnt < l) {
					failed = true;
					break;
				}
				down = false;
				cnt = 1;
			}
			// 다음 길이 낮은 경우
			else if (board[i][j] - board[i][j + 1] == 1) {
				if (down) {
					failed = true;
					break;
				}
				down = true;
				cnt = 1;
			}
			// 높이 차가 2 이상
			else {
				failed = true;
				break;
			}
		}

		if (down && cnt < l) {
			failed = true;
		}
		if (!failed) ans++;
	}

	// 열 확인
	for (int j = 0; j < n; j++) {
		int cnt = 1; // 높이가 같은 길의 수
		bool down = false; // 높이가 낮아졌는가
		bool failed = false;
		for (int i = 0; i < n - 1; i++) {
			if (down && cnt >= l) {
				cnt = 0;
				down = false;
			}

			if (board[i][j] == board[i + 1][j]) {
				cnt++;
			}
			else if (board[i][j] - board[i + 1][j] == -1) {
				if (cnt < l) {
					failed = true;
					break;
				}
				down = false;
				cnt = 1;
			}
			else if (board[i][j] - board[i + 1][j] == 1) {
				if (down) {
					failed = true;
					break;
				}
				down = true;
				cnt = 1;
			}
			else {
				failed = true;
				break;
			}
		}

		if (down && cnt < l) {
			failed = true;
		}
		if (!failed) ans++;
	}

	cout << ans;
}

시간복잡도

이중 for문을 돌고 있으므로 $O(N^2)$이다.

공간복잡도

board 배열에서 $O(N^2)$이다.