[백준] 17128번 - 소가 정보섬에 올라온 이유 (C++) 문제 및 풀이

문제) 백준 - 수학 - 소가 정보섬에 올라온 이유

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

17128번: 소가 정보섬에 올라온 이유

 

Brute Force(완전 탐색)으로 해결할 시, N이 최대 20만이기 때문에 TLE로 틀립니다. 

 

parSum[idx] : idx부터 4마리 소들의 품질 점수의 곱

idx(i) : 인덱스 처리 함수

ans : 쿼리 후 품질 점수

 

부분합을 저장하여 쿼리로 소의 품질점수가 Update될때마다 부분합을 -1 곱하고 ans를 갱신합니다.

 

C++ 소스코드)

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2015000~19999/17128_%EC%86%8C%EA%B0%80%20%EC%A0%95%EB%B3%B4%EC%84%AC%EC%97%90%20%EC%98%AC%EB%9D%BC%EC%98%A8%20%EC%9D%B4%EC%9C%A0.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions