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

https://www.acmicpc.net/problem/10836

10836번: 여왕벌

문제

크기가 M×M인 격자 형태의 벌집이 있다. 이 벌집의 각 칸에는 여왕벌이 될 애벌레들이 한 마리씩 자라고 있다. 

격자칸의 좌표계를 다음과 같이 설정한다. 제일 왼쪽 위 칸의 좌표는 (0,0)이다. 그 아래쪽 칸들의 좌표는 순서대로 (1,0), (2,0), ...등이다. 좌표가 (i,0)인 칸의 오른쪽 칸들의 좌표는 순서대로 (i, 1), (i,2), ... 등이다. 

애벌레들은 매일 에너지를 모아서 정오(낮 12시) 에 한번 자라는데, 여기에 걸리는 시간은 매우 짧아서 무시할 수 있다. 첫날 아침 모든 애벌레들의 크기는 1이고, 이러한 과정을 N일 동안 반복한다. 

각 애벌레가 자라서 크기가 커지는 정도는 하루에 +0, +1, +2의 세 가지 중 하나이다. 더하기(+) 기호는 앞으로 생략한다. 구체적으로 각 애벌레가 자라는 정도를 결정하는 규칙은 다음과 같다.

1. 제일 왼쪽 열과, 제일 위쪽 행의 애벌레들은 자신이 자라는 정도를 스스로 결정한다. 이들은 입력으로 주어질 것이다. 애벌레들이 자라는 정도를 왼쪽 제일 아래 칸에서 시작하여 위쪽으로 가면서 읽고, 제일 위쪽 칸에 도착하면 오른쪽으로 가면서 행의 끝까지 읽었다고 하자. 모든 입력에서 이렇게 읽은 값들은 감소하지 않는 형태이다.
2. 나머지 애벌레들은 자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)의 애벌레들이 다 자란 다음, 그 날 가장 많이 자란 애벌레가 자란 만큼 자신도 자란다. 

M = 4, N = 2인 예를 하나 들어보자. 다음은 각 격자에 있는 애벌레의 첫날 아침의 크기이다.

1	1	1	1
1	1	1	1
1	1	1	1
1	1	1	1

2일 동안 제일 왼쪽 열과 제일 위쪽 행에 있는 7마리의 애벌레들이 자라는 정도를 왼쪽 제일 아래칸에서 시작하여 위쪽으로 가면서 읽고, 제일 위쪽 칸에 도착하면 오른쪽으로 가면서 행의 끝까지 읽었을 때, 다음과 같다고 하자. 

• 1일: 0, 0, 1, 1, 1, 2, 2
• 2일: 1, 1, 1, 1, 1, 1, 2

첫날 저녁에 애벌레들은 아래와 같은 크기를 가진다. 예를 들어, 좌표 (1,1)의 애벌레는 왼쪽 애벌레의 크기가 1만큼 자랐고, 왼쪽 위의 애벌레가 1만큼 자랐고, 위쪽 애벌레도 1만큼 자랐으므로, 자신도 1만큼을 자란다. 또, 좌표 (3,3)의 애벌레는 규칙을 따르면 2만큼 자람을 알 수 있다.

2	2	3	3
2	2	3	3
1	2	3	3
1	2	3	3

둘째 날이 지났을 때는 동일한 과정에 따라 다음과 같이 됨을 확인할 수 있다.

3	3	4	5
3	3	4	5
2	3	4	5
2	3	4	5

격자칸의 크기, 날자 수, 날자별 제일 왼쪽 열과 제일 위쪽 행의 애벌레들이 자라는 정도를 입력으로 받아 마지막 날 저녁의 애벌레들의 크기를 출력하는 프로그램을 작성하라

입력

입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 줄에는 첫날부터 순서대로 제일 왼쪽 열과 제일 위쪽 행의 애벌레들이 자라는 정도가 다음의 형식으로 주어진다. 본문에서 보인 것과 같이, 자라는 크기를 제일 왼쪽 아래 칸에서 시작해서 위쪽으로 올라가서 제일 위쪽에 도착하면 오른쪽으로 이동하며 읽었다고 하자. 이 값들은 감소하지 않는다. 따라서, 이 수열을 처음부터 읽었을 때 0의 개수, 1의 개수, 2의 개수를 순서대로 입력에 준다. 하루에 대해서 이 세 개수들의 합은 2M-1임이 자명하다. 세 값들 중에 0이 있을 수 있다

출력

M개의 줄에 각각 M개의 자연수를 출력한다. 이는 각 애벌레의 마지막 날 저녁의 크기를 첫 행부터, 각 행에서는 왼쪽부터 제시한 것이다. (본문의 예와 동일한 형태이다.) 

 

시물레이션 문제인데, 난 이 문제를 보고 단순 완전탐색 구현밖에 떠오르지 않았다.

문제에서 하라는대로 첫열과 행은 증가값을 증가시키고, 나머지는 3방향을 확인해서 모든 구역을 완전탐색으로 증가값을 구한 뒤 증가시키는 방법으로 했다. 하지만 이렇게 하면 날짜수 1,000,000에 가로 / 세로 크기가 700이기에 무조건 시간초과가 난다. 나도 15점만 받았다 (N이 1일 때만 TC 가능)

하지만 다른 방법을 떠올리려해도 전혀 떠오르지 않아서 다른 분들의 코드를 참고하고 이해했다.

 

그 내용은 아래에서 위로 올라가고, 맨 위의 왼쪽에서 오른쪽으로 (방향성을 가지고) 값을 증가시키기 때문에 결국 값들이 오름차순으로 정렬된다.

그리고 나머지 부분들은 왼쪽, 왼쪽위, 위 방향의 증가값 중 가장 큰 값을 증가시킨다 -> 이 부분은 왼쪽값을 가지지 않는 1열을 제외하고 나머지는 모두 가장 첫번째 행, 같은 열과 같은 값을 가지게 된다. 그럼 내가 구해야하는 값은

결국 ( 2 * Size - 1 )개만 알면 나머지를 모두 출력할 수 있는 것이다.

 

< 완전탐색으로 구현해 Day가 1일 때만 통과한 코드 >

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;

// BOJ :: https://www.acmicpc.net/problem/10836

int Save[701][701];
int adj[701][701];
int Size, Day;

const int dy[] = { 0,-1,-1 };
const int dx[] = { -1,-1, 0 };

void Copy() {
	for (int i = 0; i < Size; i++)
		for (int j = 0; j < Size; j++)
			Save[i][j] = adj[i][j];
}

int isValid(int y, int x) {
	return (0 <= y && y < Size && 0 <= x && x < Size);
}

int Grow(int y, int x) {
	int maxV = 0;
	for (int i = 0; i < 3; i++) {
		int nextY = y + dy[i];
		int nextX = x + dx[i];

		if (!isValid(nextY, nextX)) continue;
		int Temp = adj[nextY][nextX] - Save[nextY][nextX];
		maxV = max(maxV, Temp);
	}
	return maxV;
}

void Print_Answer() {
	for (int i = 0; i < Size; i++) {
		for (int j = 0; j < Size; j++) {
			cout << adj[i][j] << " ";
		}
		cout << endl;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> Size >> Day;
	for (int i = 0; i < Size; i++) for (int j = 0; j < Size; j++) adj[i][j] = 1;
	for (int i = 0; i < Day; i++) {
		int Zero, One, Two;
		cin >> Zero >> One >> Two;
		vector<int> v[3];
		for (int k = 0; k < Zero; k++) v[0].push_back(1);
		for (int k = 0; k < One; k++) v[1].push_back(1);
		for (int k = 0; k < Two; k++) v[2].push_back(1);
		Copy();

		int ps = 0;
		for (int Temp = Size - 1; Temp >= 0; Temp--) {
			while (1) {
				if (!v[ps].empty()) break;
				ps++;
			}
			v[ps].pop_back();
			adj[Temp][0] += ps;
		}
		for (int Temp = 1; Temp < Size; Temp++) {
			while (1) {
				if (!v[ps].empty()) break;
				ps++;
			}
			v[ps].pop_back();
			adj[0][Temp] += ps;
		}

		for (int y = 1; y < Size; y++) {
			for (int x = 1; x < Size; x++) {
				adj[y][x] += Grow(y, x);
			}
		}
	}
	Print_Answer();

	return 0;
}

 

 

 

< 다른 분의 해설과 코드를 본 후 코드 >

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;

// BOJ :: https://www.acmicpc.net/problem/10836

int Cnt[700 * 700 + 1];
int Size, Day;

void Init_Cnt() {
	for (int i = 0; i < 2 * Size - 1; i++) Cnt[i] = 1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> Size >> Day;
	Init_Cnt();
	while (Day--) {
		int Zero, One, Two;
		cin >> Zero >> One >> Two;

		for (int Temp = Zero; Temp < Zero + One; Temp++) Cnt[Temp]++;
		for (int Temp = Zero + One; Temp < 2 * Size - 1; Temp++) Cnt[Temp] = Cnt[Temp] + 2;
	}

	for (int i = 0; i < Size; i++) {
		for (int j = 0; j < Size; j++) {
			if (j == 0)
				cout << Cnt[Size - i - 1] << " ";
			else
				cout << Cnt[Size + j - 1] << " ";
		}
		cout << endl;
	}

	return 0;
}

while문 안에서 2개의 for문이 존재하는데,

첫번째 for문은 애벌레 성장이 1인 구간이고,

두번째 for문은 애벌레 성장이 2인 구간이다.

 

성장이 0일 때는 값을 증가시켜줄 필요가 없으므로 성장이 존재하는 1과 2인 구간만 성장시켜주는 것이다.

Cnt[0] = 가장 아래 행이면서, 가장 왼쪽 열

Cnt[1] = Cnt[0]에 바로 위 값, 즉 가장 왼쪽 열이면서 아래에서 두번째 행