[백준OJ] 14890번 경사로

www.acmicpc.net/problem/14890

14890번: 경사로

---

 

-풀이-

입력을 받은 뒤, 각각 행과 열의 처음을 기준으로, 끝까지 진행을 해가며 문제에 주어진 조건이 맞는지에 대한 검사를 실행했다.

 

경우의 수는 4가지가 있다.

1. 지금까지의 높이와 현재의 높이가 같을경우, cnt++를 해준다.

 

2. 지금까지의 높이+1 == 현재의 높이 인 경우. 즉 이전보다 한칸 높아진경우, 이때는 이전까지 일정높이를 유지해오며 증가시켜오던 cnt의 값이 l보다 작다면, 경사로를 놓을 여유가 되지 않는다는 뜻이므로 불가능 판정을 내린다. 만약 cnt의 값이 l보다 같거나 크다면, 경사로를 놓을 수 있으므로, height를 갱신시켜준뒤, cnt=1로 초기화시켜준다.

 

3. 지금까지의 높이-1==현재의 높이, 즉 이전칸보다 한칸 낮아진 경우, 이때는 2번보다 좀 복잡한데, 낮아진 칸을 기준으로, 높이를 유지해가며 l칸을 전진한다. 

l칸을 전진하며 높이가 낮아진 경우, 경사로를 놓을 수 없으므로 불가능 판정을 내린다.

만약 l칸을 전진할때까지 높이가 일정한경우, 경사로를 놓을 수 있으므로 다음번 검사는 그 앞부터 하면된다.

 

4.만약 현재까지의 높이와 같지않거나, 1보다 큰 차이를 내는경우, 경사로를 놓을 수 없으므로 불가능 판정을 내리면된다.

 

-시간복잡도-

n행에 대해 각각n번 검사를 하고, n열에 대해 각각n번 검사하므로 시간복잡도는 O(N*N)이 된다.

 

-코드-

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int maze[100][100];
int n, l;


int main(){
	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> maze[i][j];
		}
	}
	int result = 0;
	for (int i = 0; i < n; i++) {
		int cnt = 1;
		int before = 0;
		int height = maze[0][i];
		bool flag = true;
		for (int j = 1; j < n; j++) {
			if (height == maze[j][i]) {
				cnt++;
			}
			else if (height+1== maze[j][i]) {
				if (cnt < l) {
					flag = false;
					break;
				}
				else {
					height = maze[j][i];
					cnt = 1;
				}
			}
			else if(height-1==maze[j][i]){
				cnt = 0;
				height = maze[j][i];
				while (maze[j][i] == height&&cnt<l) {
					j++;
					cnt++;
				}
				if (cnt < l) {
					flag = false;
					break;
				}
				j--;
				cnt = 0;
			}
			else {
				flag = false;
				break;
			}
		}
		if (flag) {
			result++;
		}
	}
	for (int i = 0; i < n; i++) {
		int cnt = 1;
		int before = 0;
		int height = maze[i][0];
		bool flag = true;
		for (int j = 1; j < n; j++) {
			if (height == maze[i][j]) {
				cnt++;
			}
			else if (height + 1 == maze[i][j]) {
				if (cnt < l) {
					flag = false;
					break;
				}
				else {
					height = maze[i][j];
					cnt = 1;
				}
			}
			else if (height - 1 == maze[i][j]) {
				cnt = 0;
				height = maze[i][j];
				while (maze[i][j] == height && cnt < l) {
					j++;
					cnt++;
				}
				if (cnt < l) {
					flag = false;
					break;
				}
				j--;
				cnt = 0;
			}
			else {
				flag = false;
				break;
			}
		}
		if (flag) {
			result++;
		}
	}
	cout << result;
}