백준 14890번 경사로 (삼성 SW 역량테스트 기출문제)

문제 링크: https://www.acmicpc.net/problem/14890

사용한 알고리즘: 구현...?


 문제에서 경사로 설치가 가능한지 여부를 묻고 있습니다.

i번째에서 i+1번째로 갈 때, 경사로 설치시 제가 생각했던 점은 다음과 같습니다.
(1) 우선 같은 높이로 이동할 시, 같은 높이의 칸의 개수를 pre로 저장해줍니다.
(2) i -> i+1 이 낮은 곳에서 높은곳으로 이동일 시, 저장해 둔 pre 가 경사로를 설치하기에 필요한 개수(L) 이상인지 판단해 줍니다.
(3) i -> i+1 이 높은곳에서 낮은곳으로 이동일 시, 이를 일종의 갚아야할 빚으로 생각하고 bool로(HavetoPay) 체크했습니다. 이후 i+1 에서 계속 이동하면서 다음 높이 변화전까지의 같은 높이의 칸의 개수(pre)를 세고, 이 값이 설치하기에 필요한 개수(L) 이상인지 판단해 줍니다.
(4) 경사로 설치에 필요한 개수 L이 1로 주었을 시 주의해서 처리해 줍니다.

위의 4가지 생각을 갖고, 주어진 칸들의 그래프의 행과 열을 따로 판단해 주었습니다.
위에 써놓은 바와 같이 L=1일 때 많은 예외들이 발생하여 이를 끈기있게 생각해 주는 것이 포인트인 것 같습니다.

	#include <bits/stdc++.h>
	using namespace std;
	//괴애애애애애애애애앵장히 구현... 예외 또 예외..!
	int N, L, arr[100][100], ans;
	bool CheckRow(int row){
	int pre = 1;
	bool HavetoPay = false;
	bool GoUp = false;
	bool OK = true;
	for (int i = 1; i < N; ++i){
	if(pre>=L&&!HavetoPay) GoUp=true;
	// 발판자리를 게속 확보
	if(arr[row][i]==arr[row][i-1]){
	pre++;
	if(pre>=L){
	if(HavetoPay){
	HavetoPay=false;
	pre=0;
	}
	else GoUp = true;
	}
	}
	// 한칸 올라가는 경우 올라갈 수 있는지 없는지가 GoUp에 저장됨
	else if(arr[row][i]==arr[row][i-1]+1){
	if(HavetoPay){
	OK=false;
	break;
	}
	if(GoUp){
	pre=1;
	GoUp=false;
	}
	else{
	OK=false;
	break;
	}
	}
	// 한칸 내려가는 경우 L만큼 빚을 진다.
	else if(arr[row][i]==arr[row][i-1]-1){
	//단 발판에 필요한 칸이 1칸이면 그대로 아무것도 없이 진행
	if(HavetoPay){
	OK=false;
	break;
	}
	if(L==1){
	GoUp=false;
	pre=0; // 그 칸을 발판을 씀
	}
	else{
	HavetoPay = true; // 빚을 짐
	pre=1;
	GoUp=false;
	}
	}
	// 차이가 1 초과인 경우
	else{
	OK=false;
	break;
	}
	}
	if(pre>=L) HavetoPay=false;
	if(HavetoPay) OK = false;
	return OK;
	}
	bool CheckCol(int col){
	int pre = 1;
	bool HavetoPay = false;
	bool GoUp = false;
	bool OK = true;
	for (int i = 1; i < N; ++i){
	if(pre>=L&&!HavetoPay) GoUp=true;
	// 발판자리를 게속 확보
	if(arr[i][col]==arr[i-1][col]){
	pre++;
	if(pre>=L){
	if(HavetoPay){
	HavetoPay=false;
	pre=0;
	}
	else GoUp = true;
	}
	}
	// 한칸 올라가는 경우 올라갈 수 있는지 없는지가 GoUp에 저장됨
	else if(arr[i][col]==arr[i-1][col]+1){
	if(HavetoPay){
	OK=false;
	break;
	}
	if(GoUp){
	pre=1;
	GoUp=false;
	}
	else{
	OK=false;
	break;
	}
	}
	// 한칸 내려가는 경우 L만큼 빚을 진다.
	else if(arr[i][col]==arr[i-1][col]-1){
	//단 발판에 필요한 칸이 1칸이면 그대로 아무것도 없이 진행
	if(HavetoPay){
	OK=false;
	break;
	}
	if(L==1){
	GoUp=false;
	pre=0; // 그 칸을 발판을 씀
	}
	else{
	HavetoPay = true; // 빚을 짐
	pre=1;
	GoUp=false;
	}
	}
	// 차이가 1 초과인 경우
	else{
	OK=false;
	break;
	}
	}
	if(pre>=L) HavetoPay=false;
	if(HavetoPay) OK = false;
	return OK;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> L;
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	cin >> arr[i][j];
	}
	}
	for (int i = 0; i < N; ++i){
	if(CheckRow(i)) ans++;
	if(CheckCol(i)) ans++;
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 14890.cpp hosted with ❤ by GitHub