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

문제링크 : https://www.acmicpc.net/problem/10836

10836번: 여왕벌

 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int arr[1401];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int M, N;
    cin >> M >> N;
 
    fill(arr, arr+2*M-1, 1);  //기본 애벌레는 1마리

    while(N--)
    {
        int idx = 0;
        for(int i=0; i<=2; i++) //0, 1, 2의 갯수
        {
            int num;
            cin >> num;
            while(num--)
            {
                arr[idx++]+=i;
            }
        }
    }

    for(int i=M-1; i>=0; i--)  //뒤에서 부터 출력
    {
        cout << arr[i] << ' '; //첫째 열
        for(int j=M; j<2*M-1; j++)
        {
            cout << arr[j] << ' ';  //두번째 열 첫째 행 ~ 두번째 열 마지막 행
        }
        cout <<'\n';
    }
    
    return 0;
}

기본 애벌레가 1마리 이므로 처음에 배열을 1로 채워준다.

 

증가해주는 방향이 ↑로 갔다가 →로 가므로 결과적으로 오름차순으로 수가 증가된다.

첫번째 열과 첫번째의 행의 값만 변화하므로 배열의 2*M-1 까지의 값만 갱신해주면 된다.

 

첫 번째 예제를 예시로 들면

1 1                                         5 6      5 6

1 1  → 1 1 1 1 → 4 5 6 1 →  4 1 → 4 6 이 된다. (변화하지 않은 값은 해당 열의 첫 값을 따른다.)

            0 1 2 

            1 1 1

            2 2 2