[BOJ 10836] 여왕벌

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

10836번: 여왕벌

 

- 문제 요약

 

크기가 M×M인 격자 형태의 벌집이 있다.

이 벌집의 각 칸에는 여왕벌이 될 애벌레들이 한 마리씩 자라고 있다.

애벌레들은 매일 에너지를 모아서 정오(낮 12시)에 한번 자라는데, 여기에 걸리는 시간은 매우 짧아서 무시할 수 있다.

첫날 아침 모든 애벌레들의 크기는 1이고, 이러한 과정을 N일 동안 반복한다. 

각 애벌레가 자라서 크기가 커지는 정도는 하루에 +0, +1, +2의 세 가지 중 하나이다.

구체적으로 각 애벌레가 자라는 정도를 결정하는 규칙은 다음과 같다.

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

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

 

 

- 알고리즘 정리

 

처음에는 문제에서 요구하는 사항을 그대로 코드로 구현하려 했으나, N과 M의 범위를 보고 시간초과가 발생할 것이라 예상했습니다. (M*M 배열을 한 번만 훑어도 최대 700^2번의 작업이 필요)

문제에서 제공한 테스트케이스를 보면서 규칙을 찾아봤는데, 0번째 열을 제외한 나머지 열들은 모두 같은 열의 0번째 인덱스와 같은 값을 가지고 있다는 것을 알았습니다.

이 점을 활용해 직접 값을 더해가며 그리디하게 코드를 작성하면 문제를 해결할 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1000001
int m,n;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>m>>n;
    vector<int>v(2*m-1,1);
    for(int i=0;i<n;i++){
    	int a,b,c;
        cin>>a>>b>>c;
        for(int j=a;j<a+b;j++){
        	v[j]++;
		}
		for(int j=a+b;j<2*m-1;j++){
			v[j]+=2;
		}
	}
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            if(j==0){
            	cout<<v[m-i-1]<<" ";
			}
			else{
				cout<<v[m+j-1]<<" ";
			}
        }
        cout<<'\n';
    }
}

코드 제출 결과