백준 / 10836 여왕벌 C++

www.acmicpc.net/problem/10836

10836번: 여왕벌

벌집 속 에벌레들이 성장하는 규칙은 다음과 같다.

 

1. 처음에 모든 칸의 에벌레는 크기가 1이다.

2. 왼쪽, 왼쪽 위, 위 칸 에벌레가 성장을 마치면 셋 중 가장 성장을 많이 한 에벌레만큼 해당 에벌레가 성장 한다.

ex) 왼쪽 1, 왼쪽 위 1, 위 1 => 왼쪽 1, 왼쪽 위 2, 위 3, 해당 칸 1 => 해당 칸 3으로 성장

3. 그렇게 주어진 N일 동안 성장한 결과를 출력한다.

 

처음 문제를 풀 때 성장한 만큼을 비교하기 위하여 copy를 하나 만들어 직전 과정과 비교하여 연산하였다.

결과는 메모리 초과.

 

그렇기 때문에 copy를 없애고 기존의 배열 내에서 연산을 하였다.

이 또한 메모리 초과.

 

메모리 초과가 날 이유는 N<=1,000,000 을 이용해 에벌레들의 배열을 최소화하는 방법 밖에 생각이 나지 않았다.

그렇기 때문에 동적할당과 free를 반복하였지만 이 또한 메모리 초과.

 

방법을 생각해보니, 비교 대상은 왼쪽, 왼쪽 위, 위 쪽과 비교를 하고, 문제를 읽어보면 첫 행과 첫 열의 성장이 이루어질 때 감소하지 않는다는 조건이 있다. 즉, 무조건 위 쪽의 성장이 제일 크다고 할 수 있다.

이를 (1,1)부터 진행하여도, 결국 해당 칸의 위쪽 칸의 성장 크기보다 클 수 없으므로, 첫 행과 첫 열에 대해서만 성장을 먼저 시키면, (0,1)=(1,1)=....=(m-1,1), (0,2)=(1,2)=...=(m-1,2) 와 같은 결과를 얻을 수 있다. 

 

처음 짰을 때보다 코드가 1/4이 되었다. 문제를 제대로 읽지 않은 나를 원망한다.

 

코드는 다음과 같다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

int m, n;
vector<int>larva;

void init_and_grow()
{
	cin >> m >> n;
	larva.resize(2 * m - 1, 1);

	for (int i = 0; i < n; i++) {
		int zero, one, two;
		cin >> zero >> one >> two;

		// 가장 자리 부분만 계산
		// 0일 때는 더하는 것 없음
		// 성장세가 감소하는 경우 없으므로
		// 무조건 0번째 열을 제외한 열은 다 같은 값 가짐
		for (int j = zero; j < zero + one; j++)
			larva[j]++;
		for (int j = zero + one; j < larva.size(); j++)
			larva[j] += 2;
	}
}

int main()
{
	init_and_grow();

	for (int i = 0; i < m; i++) {

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