[C++] BOJ(백준) 10836 여왕벌

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

10836번: 여왕벌

 

구현 문제다.

문제 그대로 구현하면 되는 문제라 특별히 설명할 부분은 없다.

 

문제에서 특이한 점이 있다면 왼쪽 위쪽 테두리의 성장 값을 줄 때 각각의 값을 주는 게 아니라

각각의 수가 연속된 개수를 준다는 점이었따.

이 부분을 어떻게 해결할 까 하다가 바로바로 값에 넣어주려 했는데

반복문은 한 번 덜 돌지라도 코드 자체가 너무 비효율적이라 일차원 배열을 생성했다.

 

처참하게 15점 받았다.

 

왼쪽 위쪽 성장을 일차원 배열에 저장하고, 해당 데이터를 2차원 배열에 반영하고, 모든 성장 계산을 날마다 반복했다.

왼쪽 위쪽을 제외한 나머지 애벌레들은 다른 애벌레의 값을 더하는 것이 아닌 복사가 되기 때문에

매일 계산을 해 줄 필요가 없다고 생각했다.

해당 부분을 마지막에 한 번만 계산하도록 코드를 수정했다.

 

어림도 없다. 83점이다.

 

왼쪽 위쪽의 성장 값들도 서로에게 영향을 주지 않으므로 일차원 배열에 성장 값을 누적해둔 뒤

나중에 한 번만 계산해도 된다.

해당 부분도 마지막에 한 번만 계산하도록 코드를 수정하니 통과했다.

 

#include <iostream>
using namespace std;

int n, m;
int arr[700][700];
int three[3];
int grow[1400];

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

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) arr[i][j] = 1;

	for (int d = 0; d < m; d++) {
		cin >> three[0] >> three[1] >> three[2];
		int index = 0;
		while (three[0]) {
			grow[index++] += 0;
			three[0]--;
		}
		while (three[1]) {
			grow[index++] += 1;
			three[1]--;
		}
		while (three[2]) {
			grow[index++] += 2;
			three[2]--;
		}			
	}

	int index = 0;
	for (int i = n - 1; i >= 0; i--)
		arr[i][0] += grow[index++];

	for (int i = 1; i < n; i++)
		arr[0][i] += grow[index++];

	for (int i = 1; i < n; i++)
		for (int j = 1; j < n; j++)
			arr[i][j] = max(arr[i - 1][j], max(arr[i][j - 1], arr[i - 1][j - 1]));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) cout << arr[i][j] << " ";
		cout << "\n";
	}
}

불필요한 연산 저리 가!