[BOJ14890] 경사로

[BOJ14890] 경사로

---

문제 링크

---

문제 설명

• 땅의 높이가 적힌 보드판을 이동하는데, 높이가 높거나 낮은 경우 경사로를 설치하여 이동할 수 있다.
• 단 경사로는, 땅의 높이가 1만큼 차이나는 경우에만 놓을 수 있고, 입력으로 주어지는 L길이로 경사로를 놓을 수 있다.
• 다음 사진은 L이 2일 때 놓을 수 있는 경우다.(출처 : 백준 온라인 저지)

• 다음 사진은 경사로를 놓을 수 없는 경우다.(출처 : 백준 온라인 저지)

• 보드판이 주어졌을 때, 경사로를 사용하거나 사용하지 않고 지나갈 수 있는 길이 몇 개인지 찾는 문제이다. 여기서 길은 한 행이나 한 열 전부를 나타내고 지나갈 수 있다는 것은 한 행이나 한 열의 끝에서 끝까지 지나가는 것.

코드 리뷰

• 일단 크게 가로길 과 세로길 로 나누어서 중첩되지 않는 큰 반복문을 2개 만들었다.(각각의 반복문은 모든 가로길과 모든 세로길을 보는 반복문)
• 각각의 길을 보기위해, 하나의 길이 선택되면 그 길의 첫 인덱스부터 마지막 인덱스까지 반복을 한 후, 마지막 인덱스에 도착하게되면 정답변수를 1 증가시킨다.
• 하나의 길을 보기위해 경우의 수 를 나눈다.
  1. 현재 블록을 기준으로 다음 블록의 높이값이 같은 경우 , 큰 경우, 작은 경우.
  2. 다음 블록의 높이가 기준 블록의 높이와 같은 경우는 기준 블록을 다음 블록으로 넘기고 카운트를 올린다.
  3. 다음 블록의 높이가 기준 블록의 높이보다 작은 경우는 먼저 높이 차이가 1이상인 경우는 break를 통해 포문을 탈출한다. 두번 째로 경사로를 만들수 있는지 없는지를 본다. if(start > board[i][j+1]) 부분 참고.
  4. 다음 블록이 더 큰 경우에 대해서도 마찬가지로 코드를 참고해보면 쉽게 이해할 수 있다.
• 경우의 수들을 거치면서, 각각의 길에 대해 마지막 인덱스에 도착하는 경우는 길을 지나갔다는 의미이므로, 정답 변수를 1 증가시킨다.
• 어려운 문제는 아니었는데, 조건을 잘못 생각해서 시간을 엄청 잡아먹었다.
• 처음 시작할 때 조건을 정확하게 나누는 연습이 더 필요할 듯.

---

/*BOJ 14890 경사로*/
#include <iostream>
using namespace std;

int N, L;
int board[105][105];

int main() {
	int ans = 0;
	scanf("%d%d", &N, &L);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
		}
	}
	for (int i = 0; i < N; i++) {
		int start = board[i][0];
		int cnt = 1;
		for (int j = 0; j < N; j++) {
			if (j == N - 1) {
				ans++;
				break;
			}
			if (start == board[i][j + 1]) { //다음 블록이랑 같은 경우
				start = board[i][j + 1];
				cnt++;
				continue;
			}
			if (start > board[i][j + 1]) { //다음 블록이 더 작은 경우
				if (start - 1 > board[i][j + 1]) break;
				int cnt2 = 0;
				for (int k = j + 1; board[i][k] == board[i][j + 1]; k++) {
					cnt2++;
				}
				if (cnt2 >= L) {
					start = board[i][j + cnt2];
					j = j + cnt2 - 1;
					cnt = cnt2-L;
					continue;
				}
				else if(cnt2<L) break;
			}
			if (start < board[i][j + 1]) { //다음 블록이 더 큰경우
				if (start + 1 < board[i][j + 1]) break;
				else if(start + 1 == board[i][j + 1]) {
					if (cnt >= L) {
						start = board[i][j + 1];
						cnt = 1;
						continue;
					}
					else if (cnt < L) break;
				}
			}
		}
	}
	for (int j = 0; j < N; j++) {
		int start = board[0][j];
		int cnt = 1;
		for (int i = 0; i < N; i++) {
			if (i == N - 1) {
				ans++;
				break;
			}
			if (start == board[i+1][j]) { //다음 블록이랑 같은 경우
				start = board[i+1][j];
				cnt++;
				continue;
			}
			if (start > board[i+1][j]) { //다음 블록이 더 작은 경우
				if (start - 1 > board[i+1][j]) break;
				int cnt2 = 0;
				for (int k = i + 1; board[k][j] == board[i+1][j]; k++) {
					cnt2++;
				}
				if (cnt2 >= L) {
					start = board[i+cnt2][j];
					i = i + cnt2 - 1;
					cnt = cnt2-L;
					continue;
				}
				else if (cnt2 < L) break;
			}
			if (start < board[i+1][j]) { //다음 블록이 더 큰경우
				if (start + 1 < board[i+1][j]) break;
				else if (start + 1 == board[i+1][j]) {
					if (cnt >= L) {
						start = board[i+1][j];
						cnt = 1;
						continue;
					}
					else if (cnt < L) break;
				}
			}
		}
	}
	printf("%d", ans);
	return 0;
}

---