[백준 14890] 경사로

문제 바로가기

14890번: 경사로

이 문제 역시 삼성 역량테스트 기출 문제이다.

크게 어렵지는 않았지만 처음 생각해낸 것보다 더 간단하게 풀 수 있었다.

 

가로줄 N번, 세로줄 N번을 봐줘야 하기 때문에 이를 함수로 구현해도 깔끔하게 안되고..

어떻게 하면 좋을까 고민하다가 결국 가로줄, 세로줄 함수를 따로 두 개를 만들어서 풀었는데 그렇게 할 필요가 없었다.

세로줄 부분을 복사해서 가로줄 밑에다가 넣어주고 2*N번만큼 가로줄을 확인해주면 되는 것이었다 !!!

세상엔 똑똑한 사람들이 참 많구나..

 

그리고 

L = 2 라 했을 때, 3 3 3 2 2 3 3 3 인 경우에는 경사로를 만들지 못하는 경우이다.

나는 이를 2차원배열에다가 저장해두고 확인했는데

그럴 필요 없이 cnt를 -L+1로 두면 굳이 메모리를 낭비하지 않고도 풀 수 있었다.

 

 

* 처음 짠 코드

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

int map[101][101];
int arr[101][101];
int N, L;

bool check_1(int n)
{
	int height = map[n][1];
	int maxx = height;
	int cnt = 0;

	for (int i = 1; i <= N; i++)
	{
		maxx = max(map[n][i], maxx);

		if (height < map[n][i])
		{
			if (map[n][i] - height > 1)
				return false;
			if (cnt < L)
				return false;
			for (int j = i-1; j >= i - L; j--)
			{
				if (!arr[n][j] && j > 0)
					arr[n][j] = 1;
				else
					return false;
			}
			height = map[n][i];
			cnt = 1;
		}
		else if (height > map[n][i])
		{
			if (height - map[n][i] > 1)
				return false;
			if (map[n][i-1] != maxx && cnt < L)
				return false;

			for (int j = i; j < i + L; j++)
			{
				if (!arr[n][j] && j <= N)
					arr[n][j] = 1;
				else
					return false;
				
			}

			height = map[n][i];
			cnt = 1;
		}
		else
		{
			cnt++;
		}
	}

	return true;
}

bool check_2(int n)
{
	int height = map[1][n];
	int maxx = height;
	int cnt = 0;

	for (int i = 1; i <= N; i++)
	{
		maxx = max(map[i][n], maxx);

		if (height < map[i][n])
		{
			if (map[i][n] - height > 1)
				return false;
			if (cnt < L)
				return false;
			for (int j = i-1; j >= i - L; j--)
			{
				if (!arr[j][n] && j > 0)
					arr[j][n] = 1;
				else
					return false;
				
			}
			height = map[i][n];
			cnt = 1;
		}
		else if (height > map[i][n])
		{
			if (height - map[i][n] > 1)
				return false;
			if (map[i-1][n] != maxx && cnt < L)
				return false;

			for (int j = i; j < i + L; j++)
			{
				if (!arr[j][n] && j <= N)
					arr[j][n] = 1;
				else
					return false;

				
			}

			height = map[i][n];
			cnt = 1;
		}
		else
		{
			cnt++;
		}
	}

	return true;
}
int main()
{

	cin >> N >> L;

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

	int route_cnt = 0;

	for (int i = 1; i <= N; i++)
	{
		if(check_1(i))
			route_cnt++;
	}

	memset(arr, 0, sizeof(arr));

	for (int i = 1; i <= N; i++)
	{
		if (check_2(i))
			route_cnt++;
	}

	cout << route_cnt << endl;

	return 0;
}

 

* 수정 코드

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

int map[201][101];
int N, L;

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

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

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			map[i + N][j] = map[j][i];
		}
	}
	int route_cnt = 0;

	for (int i = 1; i <= 2*N; i++)
	{
		int c = 1;
		int j;
		for (j = 1; j < N; j++)
		{
			if (map[i][j] == map[i][j + 1])
				c++;
			else if (map[i][j] + 1 == map[i][j + 1] && c >= L)
				c = 1;
			else if (map[i][j] - 1 == map[i][j + 1] && c >= 0)
			{
				c = -L + 1;
			}
			else
				break;
		}
		if (j == N && c >= 0)
			route_cnt++;
	}
	cout << route_cnt << endl;

	return 0;
}