15561번: 구간 합 최대? 2
첫 번째 줄에 정수 N과 Q, U, V가 입력된다. (1 ≤ N, Q ≤ 105, - 5 ≤ U, V ≤ 5) 두 번째 줄에 정수 K1, K2, ..., KN이 주어진다. (-102 ≤ Ki ≤ 102) 세 번째 줄부터 쿼리가
www.acmicpc.net
목차
- 사전 지식
- 문제 풀이
사전 지식
문제 풀이
$\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에서 가장 큰 연속합을 구한다.
어떤 배열에 대해 가장 큰 연속합을 구하는 테크닉은 여기를 참조하기 바란다.
'✏️ 알고리즘 > PS 기록' 카테고리의 다른 글
| [백준 10999번] 구간 합 구하기2 (0) | 2023.04.02 |
|---|---|
| [백준 10167번] 금광 (2) | 2023.03.30 |
| [백준 25639번] 수열과 최대 상승 쿼리 (2) | 2023.03.29 |
| [백준 2336번] 굉장한 학생 (2) | 2023.03.27 |
| [백준 12015번] 가장 긴 증가하는 부분 수열2 - 세그먼트 트리 (2) | 2023.03.27 |