fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 17128 (C++) 소가 정보섬에 올라온 이유
최초 업로드: 2025-10-12 10:38:35
최근 수정 시간: 2025-10-12 11:06:01
게시자: rlatjwls3333
카테고리: 백준
조회수: 10
# [Silver II] 소가 정보섬에 올라온 이유 [문제 링크](https://www.acmicpc.net/problem/17128) ## 문제 설명 <p>소 $N$마리가 정보섬에 올라왔다!</p> <p>소들은 정보섬 1층 앞마당에서 $A_1, A_2, A_3, \dots, A_N, A_1$의 순서대로 동그랗게 앉아 쉬고 있다. 각 소들에게는 품질 점수 $A_i$가 적힌 스티커가 붙어 있다. 욱제는 소 떼 옆에서 효빈이가 계산해 둔 어떤 계산 식을 발견했는데, 그것은 아래와 같다.</p> <p style="text-align: center;">$S = \sum_{i=1}^N(A_{i}×A_{i+1}×A_{i+2}×A_{i+3})$ (단, $A_{N+1}=A_{1}, A_{N+2}=A_{2}, A_{N+3}=A_{3}$)</p> <p>풀어 쓰자면, 원형으로 둘러 앉은 소들에 대해서, 연속한 네 마리 소들의 품질 점수를 곱한 값을 모두 더한 것이다.</p> <p>욱제는 효빈이가 학교를 떠나지 못하도록 심술부릴 작정이다. 욱제는 총 $Q$번에 걸쳐 어떤 $i$번째 소를 선택할 것이다. 그러고는 $A_i$가 적힌 스티커를 떼어내고, $A_i \times -1$이 적힌 스티커를 붙일 작정이다. 그러면 효빈이는 $Q$번에 걸쳐서 $S$를 다시 계산해야 한다. 한 번 바꾼 스티커는 다음에 또 다시 바꾸지 않는 이상 계속 유지된다.</p> <p style="text-align: center;"><img alt="" src="https://upload.acmicpc.net/46d9d347-cbae-4650-a391-b7c702663b10/-/crop/1456x1291/0,54/-/preview/" style="height: 399px; width: 450px;"> <img alt="" src="https://upload.acmicpc.net/01e9c0fd-90d8-4843-85e1-0d182a21deec/-/crop/1471x1293/0,79/-/preview/" style="height: 396px; width: 450px;"></p> <p>효빈이의 절친인 당신은 악동 욱제에게 괴롭힘 받는 효빈이를 도와 주기로 했다. 효빈이를 도와 $S$를 계산해 보자!</p> ## 입력 <p>첫째 줄에 소의 수를 나타내는 $N$과 욱제가 장난칠 횟수 $Q$가 주어진다.</p> <p>둘째 줄에 $N$마리 소들의 품질 점수 $A_i$가 순서대로 주어진다.</p> <p>셋째 줄에 욱제가 장난칠 $Q$개의 소의 번호 $Q_i$가 순서대로 주어진다.</p> ## 출력 <p>$Q$개의 줄에 걸쳐 다시 계산된 $S$의 값을 출력한다.</p> ## 풀이 미리 곱의 합을 미리 다 구해놓고, 쿼리는 입력되는 숫자 x에 대해 합의 -2배만큼 더하고, A[x]를 -1배해서 저장하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int a[200'000]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; for(int i=0;i<n;i++) cin >> a[i]; int sum=0; for(int i=0;i<n;i++) sum += a[i]*a[(i+1)%n]*a[(i+2)%n]*a[(i+3)%n]; while(q--) { int x; cin >> x; for(int i=x-4;i<x;i++) sum -= 2*a[(i+n)%n]*a[(i+n+1)%n]*a[(i+n+2)%n]*a[(i+n+3)%n]; a[x-1]*=-1; cout << sum << '\n'; } } ```