[백준 15561번] 구간 합 최대? 2

---

15561번: 구간 합 최대? 2

---

 

목차

• 사전 지식
• 문제 풀이

 

 

사전 지식

• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)
• 가장 큰 연속합을 구하는 세그트리 문제를 이해하고 있어야 한다. (링크)

 

 

 

문제 풀이

$\small{U \times (K_i + K_{i+1} + \cdots + K_j) + V \times (j-i)}$ 의미

이 식은 $\small{(UK_i + UK_{i+1} + \cdots + UK_j) + \sum_{k=i}^{j-1} V}$ 로 나타낼 수 있으며

조금 더 변환하면 $\small{(UK_i+V) + (UK_{i+1}+V) + \cdots + (UK_j+V) - V}$ 로 나타낼 수 있다.

 

즉, 각 원소를 $K_i$가 아닌 $UK_i+V$로 바꾼 배열을 arr이라고 하면 문제의 쿼리를 다음과 같이 재해석할 수 있다.

구간 $\small{[A, B]}$에 대해, arr에서 가장 큰 연속합을 구한다.

어떤 배열에 대해 가장 큰 연속합을 구하는 테크닉은 여기를 참조하기 바란다.