[백준/C++] 25606번: 장마

문제

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

---

문제 요약

장마로 인해 비가 n일 동안 내릴 예정이다.

 

t일 후에 내리는 비가 상자에 물을 채우는 양이 주어진다.

 

하루 동안 빗물을 받은 상자는 실험실에 보관되는데, 이 때 보관된 상자는 매일 물이 m만큼 증발한다.

 

q개의 질의가 주어질 때, 답을 출력한다.

 

1 t : 장마 시작 t일 후, 모든 상자에 들어있는 물의 양의 합은 무엇인가?2 t: 장마 시작 t일 후, 모든 상자에서 증발하는 물의 양의 합은 무엇인가?

---

코드

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int n, m, q;


// rain[i][0]: i일까지 내린 비의 양
// rain[i][1]: i일까지 증발한 비의 양
int rain[100010][2];

// last[i][0]: i일에 받은 물의 증발이 끝나는 상자 수
// last[i][1]: i일에 마지막으로 증발되는 비의 양
int last[100010][2];

// 현재 m만큼 증발되는 상자 수
int idx = 0;

int main() {
    // 입출력 시간 단축
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // 입력
    cin >> n >> m >> q;

    for (int i = 1; i <= n; i++) {
        int num;
        cin >> num;

        rain[i][0] = rain[i - 1][0] + num;
        rain[i][1] = rain[i - 1][1];

        // 증발이 완료된 상자가 존재할 경우
        if (last[i][0] > 0) {
            idx -= last[i][0];
            rain[i][1] += last[i][1];
        }

        // 모든 상자가 m만큼 증발 진행
        rain[i][1] += idx * m;

        // 증발이 끝나는 날 계산
        int nxt = i + (num / m) + 1;
        if (nxt <= n) {
            last[nxt][0]++;
            last[nxt][1] += num % m;
        }

        idx++;
    }

    for (int i = 0; i < q; i++) {
        int command, t;
        cin >> command >> t;

        if (command == 1) {
            cout << rain[t][0] - rain[t][1] << "\n";
        }
        else {
            cout << rain[t][1] - rain[t - 1][1] << "\n";
        }
    }

    return 0;
}

---

코드 설명

누적합을 이용하여 문제를 해결한다.

 

2차원 배열 2개를 정의한다.

 

rain[i][0] : i일까지 상자에 받은 비의 양

rain[i][1]: i일까지 증발한 비의 양

 

last[i][0]: i일에 받은 물의 증발이 끝나는 상자 수

last[i][1]: i일에 마지막으로 증발되는 비의 양

 

idx는 i일에 m만큼 증발되는 상자 수이다.

 

반복문을 통해 1일부터 n일까지 계산한다.

 

먼저, 현재까지 받은 비의 양은 이전 날까지 받은 비의 양에 오늘 받은 비의 양을 더한 값이다.

(입력 값으로 받는다.)

 

현재까지 증발한 비의 양은 이전 날까지 증발한 비의 양에 증발 오늘 증발한 비의 양을 더한 값이다.

이 때, 오늘 증발이 완료된 상자가 있으면 마지막으로 증발되는 비의 양을 더하고, idx에서 그 수만큼 빼준다.

(m만큼 증발되는 상자는 그냥 idx를 곱해서 더한다.)

 

i일에 받은 비의 양을 통해 증발이 끝나는 날을 계산할 수 있다.

ex) m이 5이고 i일에 받은 비의 양이 12이면, (12 ÷ 5) + 1 = 3일까지는 증발하고, 마지막 날에는 12 % 5 = 2만큼 증발한다.

 

위 배열을 모두 채웠다면, 이제 쿼리의 답을 찾을 수 있다.

 

1. 장마 시작 t일 후, 모든 상자에 들어있는 비의 양의 합은?

=> t일까지 상자에 받은 비의 양 - t일까지 증발한 비의 양

 

2. 장마 시작 t일 후, 모든 상자에서 증발하는 비의 양의 합은? (t일에 증발하는 비의 양)

=> t일까지 증발한 비의 양 - t - 1일까지 증발한 비의 양

---

고찰

누적합을 이용해서 시간을 단축하는 것 자체를 생각하기가 어려웠다.

 

또, 누적합을 이용한다는 것을 알고 나서도 어떻게 구체적으로 배열을 정의해야할지가 어려웠다.