[C++] 백준 10836번: 여왕벌

문제 링크

10836번: 여왕벌

문제 요약

매일 애벌레가 성장한다. 애벌레는 $M \times M$ 크기의 격자에 담겨 있는데, 초기의 크기는 모두 1로 동일하다. 가장 위의 열과 가장 왼쪽 행의 애벌레들의 성장량은 입력으로 주어진다. 이 수는 0, 1, 2 중에 하나이다. 이 값들은 감소하지 않는다.
입력은 왼쪽 아래부터, 오른쪽 위까지 꺾은 형태로 주어지게 된다.
나머지 애벌레들은 왼쪽, 왼쪽 위, 위 세 칸의 애벌레들의 성장량의 최댓값만큼 성장한다. 애벌레들이 N번 성장할 때, 마지막 상태의 애벌레들의 크기를 출력해야 한다.

접근 방법

초기에는 모든 애벌레들의 사이즈를 직접 갱신해주는 방법을 시도 했었습니다. M이 700이고, N이 100만 정도였기 때문에, 시간초과가 날 것은 당연한 일이라고 생각했습니다. 하지만 그래도 한 번 구현 연습삼아서 작성하고 제출 해봤습니다.

15점을 받은 코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 701

using namespace std;

int larva[MAX][MAX][2];

int main(void)
{
	FASTIO;

	int m, n;
	cin >> m >> n;

	for (int i = 0; i < m; i++)
		for (int j = 0; j < m; j++)
			larva[i][j][0] = 1;

	while (n--)
	{
		int r = m - 1, c = 0, num0, num1, num2;
		cin >> num0 >> num1 >> num2;

		vector<int> tmp;
		while (num0--) tmp.push_back(0);
		while (num1--) tmp.push_back(1);
		while (num2--) tmp.push_back(2);

		for (auto& i : tmp)
		{
			larva[r][c][1] = i;
			larva[r][c][0] += larva[r][c][1];

			if (!r)
				c++;
			else
				r--;
		}

		for (int i = 1; i < m; i++)
		{
			for (int j = 1; j < m; j++)
			{
				larva[i][j][1] = max(larva[i - 1][j][1], max(larva[i][j - 1][1], larva[i - 1][j - 1][1]));
				larva[i][j][0] += larva[i][j][1];
			}
		}
	}

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
			cout << larva[i][j][0] << ' ';
		cout << endl;
	}

	return 0;
}

서브태스크 문제였는데, 결과는 당연하게도 1번 서브태스크를 제외한 나머지에서 시간초과를 받았었습니다.

이후에는 0, 1, 2로 주어지는 성장량이 감소하지 않는 수열을 이룬다는 점에 주목하였습니다. 입력으로 성장량이 주어지지 않는 애벌레들은 위, 왼쪽, 왼쪽 위 세 칸의 애벌레들의 성장량을 참고해서 성장하게 됩니다. 그런데 입력으로 주어지는 성장량은 감소하지 않는 수열을 이루기 때문에, 가장 왼쪽 열을 제외한 각 행의 성장은 제일 위에 있는 행의 성장량을 따라가게 됩니다.

예를 들어 다음과 같이 성장량이 주어진다면

1 2 2
0
0

나머지 칸의 성장량은

1 2 2
0 2 2
0 2 2

이렇게 채워질 것입니다. 가장 왼쪽 열의 M개의 성장량은 어차피 가장 윗 행의 (M - 1)개의 성장량보다 작거나 같을 수밖에 없습니다. 따라서 왼쪽 열의 성장량은 무시될 수 있습니다.

만약 다음과 같이 성장량이 주어진다면

0 1 2
0
0

나머지 칸의 성장량은

0 1 2
0 1 2
0 1 2

이런 식으로 채워질 것입니다.

결과적으로 $2 \times M - 1$ 크기의 배열에 대해서만 입력을 갱신하고, 각 행을 출력할 때는, 가장 위쪽 행 부분을 참고해서 재차 출력해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int larva[1401];

int main(void)
{
	int m, n;
	cin >> m >> n;

	while (n--)
	{
		int idx = 0;
		for (int i = 0; i <= 2; i++)
		{
			int num;
			cin >> num;
			
			while (num--)
				larva[idx++] += i;
		}
	}

	for (int i = m - 1; i >= 0; i--)
	{
		cout << larva[i] + 1 << ' ';
		for (int j = m; j < 2 * m - 1; j++)
			cout << larva[j] + 1 << ' ';
		cout << '\n';
	}

	return 0;
}