10836번 : 여왕벌 [C++]

문제 링크

성공 여부(걸린 시간): 성공(1시간 9분 10초)

아이디어

해당 문제를 풀때는 무조건 문제의 조건에 대해서 잘 읽어보고 풀어야 한다.

처음에 내가 그 조건을 보기 전에는 단순 시뮬레이션 문제라고 생각했다.

그러나 문제 조건을 보고 나서 방법을 고쳐나가기 시작했다.

 

1. 매번 정직하게 전부 성장을 얼마나 할지에 대해서 저장 및 반영하는 방법 O(M*M*N)

그러나 M*M크기의 배열을 N일동안 지속적으로 초기화를 해주고 최소 N번은 해줘야 했는데

그렇게 하기위해서는 O(M*M*N)의 시간복잡도를 가지게 된다. 

그럼 문제에서 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어지는데

최악의 경우 700 * 700 * 1,000,000으로 2초는 아득히 넘겨버리기 때문에 해당방법은 불가능 하다.

 

2. 매번 2M - 1의 애벌레의 자라는 정도가 주어질때 2M - 1마리의 애벌레만 상태저장 해주기 O((2M - 1)*N)

사실 문제의 규칙을 파악하다보면 알겠지만 2M - 1마리의 애벌레가 자라는 정도에 대한 기준점으로 작용하는데

이를 오름차순으로 주어진다는 문제의 조건이 있기 때문에 결국 기준점 외의 애벌레의 자라는 속도는 

해당 애벌레의 가장 윗 기준점 애벌레가 된다는 것을 확인할 수 있다.

그래서 기준점에 해당하는 애벌레의 성장속도만 따로 관리를 해주고 제일 나중에 나머지의 배열만 채워주면 된다.

해당 열 가장 윗 행의 크기와 같음

그럼 이렇게 했을때는 시간초과로부터 안전한가? 

-> 아님 !! 2M-1에 해당하는 배열에 대해서 주어지는 입력에 맞춰 그대로 계산해준다면 O((2M - 1)*N)으로

2초를 아직도 아득히 넘어버리기 때문에 불가능함

 

3. 누적합을 통해서 2M - 1배열에 전부 접근하는 것 대신에 성장값에 대한 갱신이 가능토록 함

이 방법이 가능한 이유는 문제에서 입력으로 해당 2M - 1의 기준 애벌레들에 대한 성장을

0, 1, 2가 왼쪽 하단에서 우측상단까지 순서대로 몇개인지 수열로 받기 때문에 누적합을 통하면 1과 2의 시작

인덱스에만 접근하면 O(2*N)으로 시간복잡도를 낮출 수 있고 드디어 계산상으로 가능하다.

 

기준 애벌레의 자라는 정도에 대해서 오름차순으로 그림처럼 입력이 들어온다.예를 들어 2 3 2이 들어오면0 0 1 1 1 2 2와 같이 순서대로 성장한다는 것이다.

입력 수열에 대한 방향

그럼 누적합을 어떻게 계산할까?

예제를 기준으로 설명해보면

• 1일: 0, 0, 1, 1, 1, 2, 2
• 2일: 1, 1, 1, 1, 1, 1, 2

이라는 성장속도가 주어진다고 한다.

 

그렇다면

1. 1일차 성장은 크기가 7인 배열에 

0 0 1 0 0 1 0을 넣어준다.

 

2.  2일차 성장은

1 0 0 0 0 0 1을 넣어준다.

 

3. 최종적으로 만들어진 누적합을 하기전의 배열은

1 0 1 0 0 1 1이고

 

4. 누적합을 진행하면

1 1 2 2 2 3 4이다.

 

이를 통해 최소한의 접근으로 성장에 대한 정도의 정보를 저장할 수 있게 되었다.

이를 마지막에 기준 애벌레의 크기에 반영해주고 나머지 배열들은 해당 열 0 행의 크기로 채우면 끝.

풀이 코드

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M;
    cin >> M >> N;

    //초기 애벌레 크기 세팅
    vector<vector<int>> bees(M + 1, vector<int>(M + 1, 1));
    //성장값 누적
    vector<int> standard_bees(2 * M, 0);
    while (N--!=0) {
        //N번째 일 성장값 

        int zero, one, two;
        cin >> zero >> one >> two;
        //만약 전부 0이면 그냥 다음 입력 받으면 됨
        if (one + two == 0) {
            continue;
        }
        else{
            //zero에 입력된 값은 해당 배열의 0이 끝나는 지점-> 즉 1또는 2가 시작되는 지점
            if (one > 0) {
                standard_bees[zero]++;
                if (two > 0) {
                    standard_bees[one + zero]++;
                }
            }
            //만약 0, 1이 없고 2만 존재하는 경우
            else {
                standard_bees[zero] += 2;
            }
        }
    }
    //누적합 계산
    for (int i = 1; i < standard_bees.size(); i++) {
        standard_bees[i] += standard_bees[i - 1];
    }

    //0열 애벌레 성장시키기
    for (int i = 0; i < M; i++) {
        bees[i][0] += standard_bees[i];
    }

    // 나머지 애벌레 성장시키기
    for (int j = 0; j < M-1; j++) {
        bees[0][j + 1] += standard_bees[M + j];
        for (int i = 1; i < M; i++) {
            bees[i][j + 1] = bees[0][j + 1];
        }
    }

    //출력
    for (int i = M - 1; i >= 0; i--) {
        for (int j = 0; j < M; j++) {
            cout << bees[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}