4014. 활주로 건설

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

static int __solution(int * ary)
{
	int priv = ary[0], len = 1;
	int j;

	for (int i = 1; i < N; i++)
	{
		int diff = priv - ary[i];
		if (diff == 0) //높이가 같음
			len += 1;
		else if (diff > 1 || diff < -1) //높이 차이가 2이상 
			return 0; //경사로 설치 불가 -> 활주로 건설 불가
		else if (diff == -1) //높이 차이가 -1, 위로 가는 경사로 설치가능 여부 확인
		{
			if (len < X) //경사로를 설치할 수 없음
				return 0;
			priv = ary[i]; //재설정
			len = 1;
		}
		else //높이 차이가 1, 아래로 가는 경사로 설치가능 여부 확인 
		{
			priv = ary[i];
			len = 1;
			for (j = i + 1; j < N; j++)
			{
				if (priv == ary[j])
					len += 1;
				else
					break;
				if (len == X)
					break;
			}

			if (len < X)
				return 0;
			i = j; //j는 항상 N을 넘지 못함
			priv = ary[i];
			len = 0;
		}
	}
	return 1;
}

static int solution()
{
	int ans = 0;
	int ary[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]);
		}
	}

	for (int y = 0; y < N; y++)
		ans += __solution(board[y]);
	for (int x = 0; x < N; x++)
	{
		for (int y = 0; y < N; y++)
			ary[y] = board[y][x];
		ans += __solution(ary);
	}

	return ans;
}

핵심은 한 라인에 대해 활주로를 건설 할 수 있는지 확인하는 __solution()이다.

 

이 함수는 왼쪽에서 오른쪽으로 진행한다.

그래서 높이차가 같으면 이후 경사로를 놓을 수 있는지 여부를 확인하기 위한 길이를 증가 시킨다.

높이차가 절대값 2이상 되면 경사로를 놓을 수 없으므로 실패하고,

"높이차가 -1이 되면 위로 올라가는" 경사로 설치 여부를 판단한다. 

"높이차가 1이 되면 아래로 내려가는" 경사로 설치 여부를 판단하는데,

 

여기서는 그 동안 파악해 두었던. priv, len 이 필요가 없다.

당장 밑으로 내려가서 경사로를 놓을 수 있는 충분한 길이만 확보하면 되기 때문이다.

당장 높이차가 나는 부분을 priv로 놓고, 그 길이는 1로 설정한다.

이후 j는 그 다음 인덱스 부터 충분한 길이가 있는지 확인하는데, 같은 값이면 길이를 증가시키고 요구하는 X의 길이만큼 되는지 확인한다. 다른 값이면 바로 탈출하게 되는데, 여기서 그 길이는 X를 만족하지 못하게 된다.

 

그리고 j는 값이 다르던지 길이를 만족하여 break되어 반복문을 탈출 하기 때문에, 항상 N이 되지 못한다.

그래서 if 절 이후에 j는 경사로를 놓는 마지막 위치에 오게 되기 때문에, priv를 ary[j]로 설정하더라도, 그 길이는 0이 되는 것이다.

 

 

//주의사항 및 정리

1. priv - ary[i]를 하기 때문에 diff가 양수인 것은 priv가 더 높다는 것이다. 즉, 이 경우에는 밑으로 가는 경사로를 설치해야 하는데, 처음에는 반대로 생각했다. 이 부분은 ary[i] - priv를 하면 맞는 것이지만, 빼는 순서가 반대이기 때문에 역을 생각해야 하는데, 처음에 놓쳤던 부분이다.