[백준/14890] 경사로 (C++)

 

 

문제 해설

나에게 엄청난 좌절을 안겨준 문제이다.

처음 문제를 훑어보았을 때는 1시간이면 풀 수 있을 것이라고 착각했지만,

내 구현 능력이 아직 많이 부족하다는 것을 여실히 보여주었다.

장장 이틀에 걸친 삽질을 통해 풀 수 있었던 문제이다.

앞으로도 열심히 공부해야겠다는 자극을 받았다.

 

어쨌든, 이 문제는 이해를 바탕으로 구현하는 시뮬레이션 문제이다.

다만, 조건이 조금 까다롭기 때문에 적절한 분기 처리를 해주어야 테스트 케이스를 모두 통과할 수 있다.

나의 경우도 이 조건, 저 조건을 따지다가 시간을 모두 날려먹은 케이스이다.

 

어쨌든, 내가 풀었던 문제 풀이에 대해서 설명해보겠다.

다음과 같이 3, 2, 2, 1, 1, 1, 1, 2, 2, 3 의 높이를 가진 길과 길이 2의 경사로를 생각해보자.

 

왼쪽에 보이는 길에, 오른쪽에 보이는 경사로들을 적절히 배치해서 길을 만들 수 있는지 판단한다.

이를 위해서, 다음의 과정을 적용해보았다.

 

(1) 뒤에서부터 앞의 순서로, 현재 계단이 지난 계단들의 높이보다 1 높고, 지난 길들이 경사로의 길이 이상 연속

→ 경사로를 놓는다.

예) 위의 상황에서 이를 적용하면 다음의 상황이 된다.

 

(2) 앞에서부터 뒤의 순서로, 현재 계단이 지난 계단들의 높이보다 1 높고, 지난 길들이 경사로의 길이 이상 연속

→ 경사로를 놓는다.

예) 위의 상황에서 이를 적용하면 다음의 상황이 된다.

 

(3) 만약 인접한 두 길의 높이가 2 이상 차이난다면?

→ 이 경우에는 경사로를 놓아서 길을 만들 수 있는 상황이 아니다. 즉시 종료시킨다.

예) 이런 식으로 종료되는 경우는 다음과 같다. 마지막 길의 경우 이전 길과 높이가 2 이상 차이나므로 종료

 

위의 과정을 반복해서 최종적으로 만들어지는 길에, 실제로 길을 지나는 시뮬레이션을 적용해보고

만약 그 길이 지나갈 수 있는 길이라고 판단되면 그 길을 카운트 해주었다.

 

 

 

구현

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

using namespace std;

int map[100][100] = { 0 };
int res = 0;
int sloped[100] = { 0 };
int N, L;

void simulation()
{
	for (int i = 0; i < N; i++)
	{
		// Init
		memset(sloped, 0, sizeof(int) * 100);

		// Reverse
		int suc = 1;
		int last = map[i][N - 1];
		int j;
		for (j = N - 2; j >= 0; j--)
		{
			if (map[i][j] == last)
			{
				suc++;
			}
			else if (map[i][j] - last == 1)
			{
				if (suc >= L)
				{
					for (int k = 1; k <= L; k++)
					{
						sloped[j + k] = -1;
					}
					suc = 1;
					last = map[i][j];
				}
				else
				{
					break;
				}
			}
			else if (last - map[i][j] == 1)
			{
				suc = 1;
				last = map[i][j];
			}
			else
			{
				break;
			}
		}

		if (j >= 0) continue;

		// Normal
		suc = 1;
		last = map[i][0];
		for (j = 1; j < N; j++)
		{
			if (sloped[j] == -1)
			{
				suc = 1;
				last = map[i][j + L];
				j += L;
			}
			else if (map[i][j] == last)
			{
				suc++;
			}
			else if (map[i][j] - last == 1)
			{
				if (suc >= L)
				{
					for (int k = 1; k <= L; k++)
					{
						sloped[j - k] = 1;
					}
					suc = 1;
					last = map[i][j];
				}
				else
				{
					break;
				}
			}
			else if (last - map[i][j] == 1)
			{
				suc = 1;
				last = map[i][j];
			}
			else
			{
				break;
			}
		}

		if (j < N) continue;

		// Test
		int height = map[i][0];
		int x = 0;
		while (true)
		{
			if (x >= N)
			{
				if (height == map[i][N - 1])
				{
					res++;
				}
				break;
			}

			if (sloped[x] == 0)
			{
				x++;
			}
			else if (sloped[x] == 1)
			{
				x += L;
				height++;
			}
			else if (sloped[x] == -1)
			{
				x += L;
				height--;
			}
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N >> L;

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

	simulation();

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

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			map[i][j] = copied[j][i];

	simulation();

	cout << res << '\n';

	return 0;
}