문제 링크
백준 28303 : 자석
문제
동일한 크기의 정사각형 모양의 칸 N개가 1번부터 N번까지 일렬로 배열된 실험대가 있다. 이 실험대의
i번 칸에는 에너지 상수 ai가 설정되어 있으며, 외부의 배터리와 연결되어 있다.
이하는 실험대에 일자 모양 자석 하나를 설치하려 한다. 자석의 크기는 2부터 N까지 이하가 임의로 설정할 수 있으며, 한쪽 끝에 한 칸 크기의 N극이 있고 반대쪽 끝에 한 칸 크기의 S극이 있다. 자석의 양 극은 각각 정확히 하나의 칸 위에 놓여야 한다.
자석을 실험대에 설치하면 배터리의 에너지가 변하는데, 다음 3가지 현상이 동시에 발생한다.
- 자석의 N극이 놓인 칸의 에너지 상수만큼 배터리에 에너지가 충전된다.
- 자석의 S극이 놓인 칸의 에너지 상수만큼 배터리의 에너지가 소모된다.
- N극이 놓인 칸의 번호와 S극이 놓인 칸의 번호의 차에 K를 곱한 만큼 배터리에서 에너지가 소모된다. 두 수의 차는 큰 수에서 작은 수를 뺀 값이다.
이하는 자석을 실험대에 설치하여 배터리를 최대한 충전하고 싶다. 이하를 도와 자석을 놓기 전과 비교해서 얻을 수 있는 배터리의 에너지 변화의 최댓값을 구해보자. 실험의 결과로 배터리의 에너지가 실험 전과 비교하여 감소할 수도 있다.
입력
첫 번째 줄에 두 정수 N과 K가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 500,000) (0 ≤ K ≤ 2,000)
두 번째 줄에 N개의 정수 a1, a2, ... aN이 공백으로 구분되어 주어진다. (0 ≤ ai ≤ 10^9)
출력
첫 번째 줄에 자석을 놓기 전과 비교해서 얻을 수 있는 배터리의 에너지 변화의 최댓값을 출력한다.
아이디어
N의 범위가 50만이기 때문에 O(N^2)의 시간복잡도를 필요로하는 방법으로는 문제를 해결할 수 없다. 따라서 수식의 관계에서 누적합(prefix sum)을 사용하여 연산의 시간복잡도를 줄여야한다.
j < i 이고 i 위치에 N극, j위치에 S극이 오는 경우에는 다음과 같은 식으로 에너지 변화를 계산할 수 있다.
$$
e_i - e_j - K \times (i-j)
$$
$$
= (e_i - K \times i) - (e_j - K \times j)
$$
이렇게 표현된 수식은 i에 영향받는 항과 j에 영향받는 향으로 나뉘게 된다.
1) j에 영향받는 항
j < i 라는 제약을 만족하는 범위에서 j를 증가시켜가면서 해당 인덱스 범위까지 고려했을 때의 최솟값을 저장하는 방식으로 j에 대한 항의 최솟값을 계산할 수 있다.
2) i에 영향받는 항
i는 반복문을 통해 2에서 시작해서 N까지 값을 계속 증가시켜나가기 때문에 이번 반복에서 새롭게 고려하게 된 범위에 대해 연산한 뒤에 기존값과 비교해서 더 큰 값으로 갱신해나가면 된다.
아래 그림을 보면 더 이해하기 쉬울 것이다.
반대로 자석을 놓는 경우에는 에너지 상수가 저장된 배열 자체를 뒤집어서 계산하는 방식으로 계산할 수 있다. (인덱스 차이로 계산되기 때문에 인덱스 상관없이 그냥 뒤집어도 된다.)
알고리즘 : 코드
import sys
input = sys.stdin.readline
def I():
def solve(N, K):
minJSN = 999999999999999999
minJNS = 999999999999999999
maxEnergy = -999999999999999999
Energy = [0] + energy
reverseEnergy = [0] + list(reversed(energy))
for i in range(2, N + 1):
j = i - 1
minJSN = min(minJSN, Energy[j] - K * j)
minJNS = min(minJNS, reverseEnergy[j] - K * j)
maxEnergy = max(
maxEnergy, Energy[i] - K * i - minJSN, reverseEnergy[i] - K * i - minJNS
)
return maxEnergy
N, K = map(int, input().split())
energy = list(map(int, input().split()))
print(solve(N, K))
I()
회고
UCPC 2023 예선 open contest에서 나왔던 문제이다. A랑 D 2솔 한 다음에 건드려본 문제인데 거의 다 풀었었는데? "에너지 변화의 최댓값"을 출력하라는 의미를 절댓값의 최댓값을 의미하는 것으로 착각해서 계속 틀리고 있었다.
문제를 잘 읽도록 하자. 그리고 구현할 때 배열에 K값에 따른 변화값도 기록해서 저장한다음 (e.g., e[1], e[2]+K, e[3]+2K...) 양 끝에서 시작하여 quick sort처럼 진행해서 푸는 방법을 생각만하다가 누적합으로 방향을 틀었었는데 백준 난이도 평가 하신거 보니까 내가 생각하던 방법 두 포인터(two pointer)로도 푸신 분이 계셨다. 다음에 시간되면 생각했던 방법으로도 구현해봐야겠다.