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

www.acmicpc.net/problem/10836

10836번: 여왕벌

1. 접근

문제에서 주어진 그대로 첫 row, col은 입력대로 증가시키고

이 외의 원소는 3방향 중 가장 큰 증가량을 조사하면서 하나하나 증가시켰다.

하지만 700*700 크기의 배열을 1000000에 대해서 해당 연산을 하니 당연히 시간초과

 

 

2. 풀이

규칙을 찾아야 했는데, "오름차순으로 주어진 0,1,2가 몇번 연속적으로 쓰여있는지"가 입력으로 주어지므로

'첫 번째 열의 원소'들은 입력대로 증가시키고 '나머지 원소들'은 같은 열 첫번 째 행의 원소만큼 똑같이 증가한다.

 

따라서 첫번째 열의 마지막 행~첫번째 행, 첫번째 행의 두번째 열~마지막 열을 나타내는 배열에

누적증가량을 저장하고 마지막에 출력에 이용한다.

 

즉, cnt 배열은

1. [0] ~ [M-1]이 첫번째 열의 마지막 행~첫번째 행의 누적 증가량이고

2. [M] ~ [2M - 1]이 첫번째 행의 두번째 열~마지막 열의 누적 증가량이다.

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

using namespace std;

int M, N, cnt[700 * 700 - 1] = { 0, }, num[3];
pair<int, int> dir[3] = { { 0, -1 }, { -1, -1 }, { -1, 0 } };

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> M >> N;

	for (int i = 0; i < N; i++){
		cin >> num[0] >> num[1] >> num[2];

		for (int j = num[0]; j < num[0] + num[1]; j++)
			cnt[j]++;
            
		for (int j = num[0] + num[1]; j < num[0] + num[1] + num[2]; j++)
			cnt[j] += 2;
	}

	for (int i = 0; i < M; i++){
		for (int j = 0; j < M; j++){
			if (j == 0){
				cout << 1 + cnt[(M - 1) - i] << " ";
			}
			else{
				cout << 1 + cnt[(M - 1) + j] << " ";
			}
		}
		cout << "\n";
	}
	cout << "\n";


	return 0;
}