BOJ-10836 여왕벌

접근

• 행렬을 가지고 입력받을 때마다 업데이트를 해주는 방식으로 하면 시간복잡도가 3*(2*M-1)*N번(약 4,200,000,000)의 연산이 이루어지므로 시간초과를 받게된다.
• 행렬을 조작하지 않고 행렬의 왼쪽 첫 열과 위쪽 첫 행을 1400 길이의 배열(tmp)로 바꾸어 저장하고 규칙을 찾았어야 했는데 이때 시간이 조금 많이 걸렸었다. 규칙은 아래와 같다.

첫 번째 행은 tmp 배열에 저장된 값(tmp[M-i-1])을 가져온다.
그 이후 행들은 자신의 바로 위에 저장된 값(tmp[M+j-1])을 가져온다.

• 행렬을 조작하지 않고 tmp배열을 사용하여 연산 횟수를 3*(2*M-1)*N번에서 (2*M-1)*N번(약 1,4000,000)번으로 줄여 최적화를 적용하고 시간내에 문제를 해결할 수 있었다.

코드(C++)

#include <iostream>
#define FIO  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;
int M,N,tmp[1401],a,b,c;

int main(){
    FIO;
    cin>>M>>N;
    
    for(int i=0;i<N;i++){
        cin>>a>>b>>c;
        for(int j=a;j<2*M-1;j++) tmp[j] += (j<a+b ? 1:2);
    }
    
    for(int y=0;y<M;y++){
        for(int x=0;x<M;x++) cout<<(x==0 ? tmp[M-y-1] : tmp[M+x-1])+1<<" ";
        cout<<"\n";
    }
    return 0;
}

결과