[BOJ] 28303: 자석 (C++)

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

28303번: 자석

걸린 시간 : 49분 11초

---

UCPC 2023 예선 문제다.

 

문제가 이상한 말을 많이 하지만 돌려돌려 생각해보면 문제 자체는 이해하기 쉽다. a[i] - a[j] - abs(i-j) * K 값을 구하라는 것이다.

 

단순히 생각해 봤을 때, 변수가 i, j 이므로 단순히 탐색을 한다면 O(N^2) 일 것이다. 하지만 N의 범위가 500000이다. 보통 몇천 단위를 넘어가면 의도적으로 O(N^2) 를 막아놓은 것이다. 게다가 이 문제는 대회문제이므로, 수학적인 아이디어가 조금은 필요할 것이라고 생각하고 종이를 꺼내들고 끄적거렸다.

 

"수학적인 아이디어" 라는 생각을 하니 일반항부터 생각났다. 아까 말한 a[i] - a[j] - abs(i-j) * K  를 (a[i] - i * K ) - (a[j] - j * K ) 로 풀어해칠  수 있음이 생각났다. (일단 i > j 인 가정. j > i 인 경우는 다시 또 하면 된다!) 이러면 하나의 일반항으로 생각할 수 있게 된다. 따라서 예제에 나온 배열을 이 일반항을 토대로 배열을 생각해봤다.

해당 배열은 25, 12, 18, 7, -4 이다. i > j 인 경우이므로 이 때 최댓값은 막무가내로 생각해도 6이다. (18-12)

 

중요한 것은, 이걸 O(N^2) 이내에 해야 한다는 것. 정렬이나 이분 탐색같은 아이디어는 없으니 logN 이 끼어들 자리가 없어 아마 O(N) 일 것으로 예상하고 접근해본다.

생각보다 쉽다. i를 증가시키면서 그 전의 최솟값들만 계속 갱신시키면서 계산하면 최댓값이다. 즉, (a[i] - i * K ) - (a[j] - j * K ) 에서 j에 해당하는 값을 최소로 만들면 되니까, 이 값만 최소로 계속 갱신한다는 것이다.

 

그리고 나서, j > i 인 경우는 이 수열을 뒤집어서 생각하면 된다. 항상 이런 문제를 풀 때는 예제 배열을 직접 써보면서 따져가야 실수를 하지 않는다.

 

#include <bits/stdc++.h>
using namespace std;

int N, K, ans = -2100000000;
int a[500001], energe[500001], mn;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 0; i < N; i++)
		cin >> a[i];
	//순방향
	for (int i = 0; i < N; i++) {
		energe[i] = a[i] - K * i;
	}
	mn = energe[0];
	for (int i = 1; i < N; i++) {
		ans = max(energe[i] - mn, ans);
		mn = min(mn, energe[i]);
	}
	//역방향
	for (int i = 0; i < N; i++) {
		energe[i] = a[N-i-1] - K * i;
	}
	mn = energe[0];
	for (int i = 1; i < N; i++) {
		ans = max(energe[i] - mn, ans);
		mn = min(mn, energe[i]);
	}
	cout << ans;
	return 0;
}