PS(Problem Solving)/백준_BOJ
[백준] 17128번 - 소가 정보섬에 올라온 이유 (C++) 문제 및 풀이
초코칩프라푸치노
2022. 1. 28. 16:21
문제) 백준 - 수학 - 소가 정보섬에 올라온 이유
https://www.acmicpc.net/problem/17128
17128번: 소가 정보섬에 올라온 이유
첫째 줄에 소의 수를 나타내는 N과 욱제가 장난칠 횟수 Q가 주어진다. (4 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) 둘째 줄에 N마리 소들의 품질 점수 Ai가 순서대로 주어진다. (1 ≤ |Ai| ≤ 10) 셋째 줄에
www.acmicpc.net
Brute Force(완전 탐색)으로 해결할 시, N이 최대 20만이기 때문에 TLE로 틀립니다.
parSum[idx] : idx부터 4마리 소들의 품질 점수의 곱
idx(i) : 인덱스 처리 함수
ans : 쿼리 후 품질 점수
부분합을 저장하여 쿼리로 소의 품질점수가 Update될때마다 부분합을 -1 곱하고 ans를 갱신합니다.
C++ 소스코드)
Full Code)
GitHub - Chocochip101/BOJ_Solution: BOJ Solutions
BOJ Solutions. Contribute to Chocochip101/BOJ_Solution development by creating an account on GitHub.
github.com
반응형