문제
https://www.acmicpc.net/problem/30160
30160번: 제곱 가중치
첫 번째 예시에서, $a = (1, 2, 3, 4)$ 이므로, $1^{2} \cdot a_{1} = 1$, $2^{2} \cdot a_{1} + 1^2 \cdot a_{2} = 6$, $3^{2} \cdot a_{1} + 2^{2} \cdot a_{2} + 1^{2} \cdot a_{3} = 20$, 그리고 $4^{2} \cdot a_{1} + 3^{2} \cdot a_{2} + 2^{2} \cdot a_{3
www.acmicpc.net
풀이
N이 10만이므로 모든 결과값을 다 구해주는 것은 적절하지 않다.
각 결과값을 효율적으로 구하는 법이 필요하다.
우린 두가지 고민을 할 수 있다.
1. 각 결과값마다 한번에 구해준다.
이 방법은 모르겠다. 어려워보인다.
2. 지금 구해야할 결과값을 이전결과값을 이용해 구해준다.
이를 정리해보자.
k번째(1<k<=N) 결과값을 구할 때 식을 이렇게 나타낼 수 있다.
a1 * k^2 + a2 * (k-1)^2 + ... + ak-1 * 2^2 + ak * 1^2
k-1번째 결과값은 다음과 같다.
a1 * (k-1)^2 + a2*(k-2)^2 + ... + ak-1 * 1^2
Bk를 k번째 결과값이라 정의하자
Bk-1 * Xk = Bk를 만족시키는 Xk를 찾는 것이 어려워보인다. 항의개수가 많으므로 Bk/Bk-1을 하기엔 무리가 있다.
Bk-1 + Xk = Bk를 만족시키는 Xk를 찾아보자. Bk - Bk-1을 해본다.
그렇다면 식은 이렇게 정리된다.
Xk = a1* (k^2-(k-1)^2) + a2 * ((k-1)^2-(k-2)^2) + ... + ak-1 * 3 + ak * 1
자연수 i에 대해 (i^2 - (i-1)^2) = (i^2 - (i^2-2i+1)) = 2i - 1 즉 홀수이다.
다시 정리하면 Xk = a1 * (2k-1) + a2 * (2k-3) + ... + ak-1*(2k-(2k-3)) + ak*(2k-(2k-1)) = 2k*(a1 + a2 + ... + ak) - (a1 + 3a2 + ... + (2k-1)ak)
따라서 누적합을 이용하면 Xk를 O(1)에 구할 수 있고, 정답을 O(N)으로 구할 수 있다.
코드(python)
oddimos[0],imos[0] = A[0],A[0]
for i,v in enumerate(A):
if i == 0:
continue
imos[i] = imos[i-1] + v # 일반 누적합 계산
oddimos[i] = oddimos[i-1] + (2*i+1)*v # 홀수 누적합 계산
ans = [A[0]]
for i in range(1,N):
k = i + 1 # k
p = ans[-1] # 이전 결과값
xk = 2*k*imos[i] - oddimos[i]
ans.append(p + xk)
'알고리즘문제풀이' 카테고리의 다른 글
| 백준 30094 그래서 나는 사진을 그만두었다 (0) | 2023.09.25 |
|---|---|
| 백준 30027 비밀의 화원 (1) | 2023.09.22 |
| 백준 28102 단순한 그래프와 이상한 쿼리 풀이 (0) | 2023.09.14 |
| 백준 8983 사냥꾼 풀이 (1) | 2023.09.13 |
| 백준 29619 나무나무나 심어야지 (python) (2) | 2023.09.07 |