백준 14890번 경사로 (Simulation)

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

14890번: 경사로

 

시뮬레이션에 속하는 문제라 예외처리가 많아서 소스코드 양이 생각보다 길다.

경사로를 놓기 위해서 고려해야 하는 경우는

1) 현재 값과 다음 값이 같은 경우

2) 현재 값이 다음 값보다 1 큰 경우

3) 현재 값보다 다음 값이 1 작은 경우

4) 그 외 경사로를 놓을 수 없는 경우로 나눌 수 있다.

 

2, 3번인 경우가 까다로운데 반복문을 수행하면서 배열이 끝날때까지 경사로를 놓을 수 있는지 체크했다.

그리고 4번은 fail이므로 따로 신경쓰지 않아도 되지만 1~ 3번이더라도 이미 경사로를 놓은 경우에는 fail이므로 따로 배열변수(소스코드에서는 변수명: t)를 이용해야 한다.

 

시뮬레이션이라 예외처리만 잘하면 되므로 따로 설명할 부분은 없다.

문제에서 행과 열 두가지 모두 값을 구해야 하는데 solve 함수를 한번만 사용하기 위해서 열을 행으로 만드는 배열변수(소스코드에서 배열변수명 :b)를 따로 이용했다.

 

<소스코드>

#include<iostream>

using namespace std;

int a[101][101];
int b[101][101];
int N, L;

bool solve(int a[]) {
	int t[100] = { false, };

	for (int i = 0; i < N - 1; i++) {
		if (a[i] == a[i + 1]) {
			continue;
		}
		else if (a[i] == a[i + 1] + 1) {
			if (L == 1) {
				if (t[i+1] == true) {
					return false;
				}
				else {
					t[i+1] = true;
				}
			}
			else {
				for (int j = i + 1; j < i + L; j++) {
					if (j >= N) return false;

					if (a[j] != a[j + 1]) {
						return false;
					}
					else {
						if (t[j] == false && t[j + 1] == false) {
							t[j] = true;
						}
						else {
							return false;
						}
					}
				}
				t[i + L] = true;
			}
		}
		else if (a[i] + 1 == a[i + 1]) {
			if (L == 1) {
				if (t[i] == true) {
					return false;
				}
				else {
					t[i] = true;
				}
			}
			else {
				for (int j = i; j > i + 1 - L; j--) {
					if (j < 0) return false;

					if (a[j] != a[j - 1]) {
						return false;
					}
					else {
						if (t[j] == false && t[j - 1] == false) {
							t[j] = true;
						}
						else {
							return false;
						}
					}
				}
				t[i + 1 - L] = true;
			}
		}
		else {
			return false;
		}
	}
	return true;
}

int main(void) {
	cin >> N >> L;

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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			b[i][j] = a[j][i];
		}
	}

	int ans = 0;

	for (int i = 0; i < N; i++) {
		ans += solve(a[i]);
		ans += solve(b[i]);
	}
	
	cout << ans << "\n";

	return 0;
}