[백준/25606] 장마 (Python)

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

25606번: 장마

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:37:35

 

---

 

문제 설명

 

기상과 자연재해 수업에서 교수님이 장마로 인해 내일부터 비가 N일 동안 내릴 예정이니 장마에 관한 주제로 텀 프로젝트를 진행하라는 과제를 내주었다.

다빈이는 기상 조건에 따라 비가 얼마나 내리고 증발하는지에 대한 데이터를 만들고, 이 데이터를 활용한 장마 강수량 예측 AI 모델을 만들어서 제출하기로 하였다. 그래서 데이터를 수집하기 위해 매일 새로운 아크릴 상자를 대학교 옥상에 두어 아크릴 상자에 들어있는 물의 양을 측정했다.

장마 시작 t일 후에 내리는 비는 상자에 a_t만큼 물을 채우는데, 하루 동안 빗물을 받은 상자는 실험실에 보관한다. 이때 보관된 상자는 매일 물이 M만큼 증발한다. 만약 상자에 있는 물이 M보다 적다면 남은 물이 모두 증발하게 된다.

다빈이는 이것을 주제로 텀 프로젝트를 완성하였고, 발표를 성공적으로 끝마쳤다. 하지만 제출할 때 깜빡하고 데이터를 같이 제출하지 못하였는데, 이것을 확인한 교수님이 데이터가 정확한지 확인하기 위해 기습적으로 Q개의 질문을 하였다. 다빈이가 당황하지 않고 모든 질문에 답할 수 있게 아래 질문에 대한 답을 구해주자.

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

 

입력 및 출력

 

입력

 

첫째 줄에 N, M, Q가 주어진다. (1 <= N, Q <= 100,000, 1 <= M <= 10,000)

둘째 줄에 길이가 N인 수열 a_1, a_2, a_3, ... , a_N이 공백을 사이에 두고 주어진다. (1 <= a_i <= 10,000)$

셋째 줄부터 Q+2번째 줄에는 본문에 주어진 질문이 주어진다. (1 <= t <= N)

입력으로 주어지는 모든 값은 정수이다.

 

출력

 

각 질문에 대한 정답을 한 줄에 하나씩 출력한다.

 

입력 예시

 

8 3 3
3 5 10 8 7 1 2 7
1 5
1 3
2 6

 

출력 예시

 

16
12
9

 

 

---

 

풀이

 

누적 합으로 풀이해 보자. 총 물의 양과 총 증발량의 누적합을 sum, evap이라고 두면

• 쿼리 1 : 총 물의 양 - 총 증발량, sum[i] - evap[i]
• 쿼리 2 : 당일 증발량, evap[i] - evap[i-1]

이 성립한다.

여기서 또, 우리는 각 상자의 증발량을 계산할 필요가 있다.

• i번째 시점에 들어온 상자가 rain[i]만큼의 물을 보유하고 있다고 하자.
• 그렇다면 [i+1, i+rain[i] / M] 구간동안 지속적으로 M만큼의 물이 증발한다.
• 그리고 i + rain[i] / M + 1번째 날, 남은 rain[i] % M만큼의 물이 증발할 것이다.
• 물이 남아있는 상자를 카운트하고, i번째에 마지막으로 증발하는 상자 개수와 그 양을 카운트하자.
  • i번째에 증발하는 상자 개수만큼 상자가 줄어들고, 그 값만큼 당일 증발량이 증가한다.
  • 또한 남은 상자 개수 * M만큼 당일 증발량이 증가한다.
  • 당일 상자 개수, i + rain[i] / M + 1번째 날의 상자 개수, 그 날의 증발량을 업데이트한다.

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

N, M, Q = map(int, input().split())
rain = list(map(int, input().split()))
sums = [0]*(N+1)
evap = [0]*(N+1)
q = [[0]*2 for _ in range(N)]
cnt = 0

for i in range(N) :
  sums[i+1] = rain[i] + sums[i]
  cnt -= q[i][0]
  evap[i+1] += q[i][1] + cnt * M
  idx = i+1 + rain[i] // M
  if idx < N :
    q[idx][0] += 1
    q[idx][1] += rain[i] % M
  cnt += 1
  
for i in range(1, N+1) :
  evap[i] += evap[i-1]

for _ in range(Q) :
  q, c = map(int, input().split())
  if q == 1 :
    print(sums[c] - evap[c])
  else :
    print(evap[c] - evap[c-1])

풀이 완료!