4014

static int N, X;
static int board[20][20];

static bool is_available(int * arr)
{
	int priv = arr[0], length = 1;

	for (int x = 1; x < N; x++)
	{
		int diff = arr[x] - priv;

		if (diff < -1 || diff > 1) //높이차가 2이상인 경우,
		{
			return false;
		}
		else if (!diff) //같은 경우,
		{
			length += 1;
		}
		else if (diff == 1) //위로 올라가는 경사로를 설치할 수 있는지 확인.
		{
			if (length < X)
				return false;

			priv = arr[x];
			length = 1;
		}
		else if (diff == -1) //아래로 내려가는 경사로를 설치할 수 있는지 확인.
		{
			length = 1;
			priv = arr[x++];

			for (; x < N && length < X; x++, length++)
			{
				if (arr[x] != priv)
					break;
			}

			if (length < X)
				return false;

			//special, 
			length = 0;
			priv = arr[--x];
		}	
	}

	return true;
}

static int solution(void)
{
	int ret = 0;
	int line[20];

	scanf("%d %d", &N, &X);
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
			scanf("%d", &board[y][x]);
		if (is_available(board[y]))
			ret += 1;
	}

	for (int x = 0; x < N; x++)
	{
		for (int y = 0; y < N; y++)
			line[y] = board[y][x];
		if (is_available(line))
			ret += 1;
	}

	return ret;
}

 

가장 쉬운 경우는 아래의 케이스다.

모든 높이가 같은 경우이다.

 

아래의 경우를 X = 2, 에 대해서 고려해보면,

높이가 2 에서 3으로 갈 때 에는 경사로를 놓을 수 있는 충분한 거리가 있음을 누적된 length라는 변수를 통해 쉽게 알 수 있다. 또, 경사로를 놓고 나서는 다음에 사용할 x에 대해서 priv와 해당 priv의 거리가 1로 설정되고 있다.

마치 전체 반복문 시작 전에 x = 0, 에 대해서 priv와 length를 설정하는 것 처럼 말이다.

 

그러나 이후 3 에서 2로 다시 갈 때 에는 살짝 생각해야 할 부분이 있다.

else if (diff == -1) 에서 x는 "↘" 위치에 있다. 그래서 경사로를 위해 필요한 밑변의 길이가 일단 1이 되는 것이다.

그래서 해당 위치는 고려 되었기 때문에 x를 다음 위치로 이동 시키는 것이다.

역시 높이가 같기 때문에 length는 2가 되어 반복문을 탈출하게 된다.

 

이제 여기서 주의 할 점은 다음과 같다.

높이가 2인 곳은 모두 경사로를 위해 사용되었기 때문에 else if (diff == 1)과 같이 생각하게 된다면

논리적으로 오류가 발생하게 된다. 이에 대해, 그 흐름을 살펴보면,

priv는 높이가 1인 "↘" 위치로 설정되고, 그 길이는 1이 된다. 여기까지는 뭐 맞는 거 같다.

그러나 2에서 1로 떨어지기 때문에 경사로를 설치 할 수 있는지 여부를 다시 확인해야 하는 코드가 필요해진다.

 

그러나 priv의 위치를 높이가 2인 "→" 로 설정하게 되면 추가 코드 필요 없이 반복문을 다시 돌면서 해당 반복문 내에 코드로 처리하게 되므로 더 간단하게 처리 할 수 있다.