[BOJ/백준] 28303 : 자석

문제 링크
백준 28303 : 자석

문제

동일한 크기의 정사각형 모양의 칸 N개가 1번부터 N번까지 일렬로 배열된 실험대가 있다. 이 실험대의
i번 칸에는 에너지 상수 ai가 설정되어 있으며, 외부의 배터리와 연결되어 있다.

이하는 실험대에 일자 모양 자석 하나를 설치하려 한다. 자석의 크기는 2부터 N까지 이하가 임의로 설정할 수 있으며, 한쪽 끝에 한 칸 크기의 N극이 있고 반대쪽 끝에 한 칸 크기의 S극이 있다. 자석의 양 극은 각각 정확히 하나의 칸 위에 놓여야 한다.

자석을 실험대에 설치하면 배터리의 에너지가 변하는데, 다음 3가지 현상이 동시에 발생한다.

1. 자석의 N극이 놓인 칸의 에너지 상수만큼 배터리에 에너지가 충전된다.
2. 자석의 S극이 놓인 칸의 에너지 상수만큼 배터리의 에너지가 소모된다.
3. 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)로도 푸신 분이 계셨다. 다음에 시간되면 생각했던 방법으로도 구현해봐야겠다.