백준 10836: 여왕벌 C++

www.acmicpc.net/problem/10836

10836번: 여왕벌

1. 처음에 아무생각없이 직관적으로 풀었다가 시간초과가 떠버렸다....

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m; // 크기, 날짜 수
int map[701][701];
int map_before[701][701];
int datas[3];

int biggest_growth(int i, int j)
{
	int result = 0;
	result = max(result, map[i-1][j-1] - map_before[i - 1][j - 1]);
	result = max(result, map[i][j-1] - map_before[i][j - 1]);
	result = max(result, map[i-1][j] - map_before[i - 1][j]);

	return result; //주변 중 가장 크게 자란 곳!
}

int add(int index)
{
	if (index <= datas[0])
	{
		return 0;
	}
	else if (index > datas[0] && index <= (datas[0] + datas[1]))
	{
		return 1;
	}
	else if (index > (datas[0] + datas[1]) && index <= (datas[0]+datas[1] + datas[2]))
	{
		return 2;
	}
}

void growth()
{
	// (1,1) 부터 (m-1,m-1) 까지
	// 행 1부터 m-1까지
	for (int i = 1; i < m; i++)
	{
		for (int j = 1; j < m; j++)
		{
			map_before[i][j] = map[i][j];
			map[i][j] += biggest_growth(i, j);
		}
	}
}



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

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
		{
			map[i][j] = 1; //처음에는 다 1
		}
	}

	for (int i = 0; i < n; i++)//각 일 수
	{
		int index = 1;
		for (int k = 0; k < 3; k++)
		{
			cin >> datas[k];
		}
		// 정해지는 애들 미리 성장시키기
		for (int j = m - 1; j >= 0; j--)
		{
			map_before[j][0] = map[j][0];
			map[j][0] += add(index++);
		}
		for (int j = 1; j < m; j++)
		{
			map_before[0][j] = map[0][j];
			map[0][j] += add(index++);
		}


		//나머지 차근차근 성장해나가기
		growth();
	}


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

	return 0;
}

2. 블로그 검색후 수정

- 애벌레가 매번 성장할때 마다 갱신해버리면  O(M^2) 라 시간초과 떠버림

- 증가율을 저장해 놨다가 한번에 갱신하자

- 우리가 미리 정해주는 맨 왼쪽 열과 맨 위쪽 행 말고는 map자기 위에 값으로 갱신됨!!

 난 이걸 생각치도 못했다....ㅎ

 

참고:

m.blog.naver.com/PostView.nhn?blogId=hoyo1744&logNo=221526068140&proxyReferer=https:%2F%2Fwww.google.com%2F

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int arr[701][701];
int outside[1500];

int main()
{

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

	for (int i = 1; i <= 2 * n - 1; i++)
	{
		outside[i] = 1;
	}


	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		for (int i = a + 1; i <= a + b; i++)
			outside[i] += 1;
		for (int i = a + b + 1; i <= 2 * n - 1; i++)
			outside[i] += 2;


	}

	int row = n;
	int col = 1;

	for (int i = 1; i <= 2 * n - 1; i++)
	{
		if (row == 1)
		{
			arr[row][col] = outside[i];
			col++;
		}
		else
		{
			arr[row][col] = outside[i];
			row--;
		}
	}


	for (int i = 2; i <= n; i++)
	{
		for (int j = 2; j <= n; j++)
			arr[i][j] = arr[1][j];
	}



	for (int i = 1; i <= n; i++)

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