[BOJ 25634 // C++] 전구 상태 뒤집기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25634번 문제인 전구 상태 뒤집기이다.
문제는 아래 링크를 확인하자.

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

25634번: 전구 상태 뒤집기

주어진 문제는 현재 켜져있는 전구들의 밝기에서 "건드렸을 때 가장 밝기가 밝게 변화하는 하나의 구간"을 찾아 조작해 전구를 키는 문제로 생각할 수 있다. 구간에 포함되는 전구가 원래 켜져있었다면 밝기는 그 전구의 밝기만큼 감소할 것이고, 꺼져있었다면 그 전구의 밝기만큼 증가할 것이기 때문이다. 즉, 켜져있는 전구를 건드릴 때는 밝기가 감소하고 꺼져있는 전구를 건드릴 때는 밝기가 증가하는 형태의 배열을 만들어 가장 큰 연속구간합을 찾는 것으로 문제를 해결할 수 있다.

 

한편, 주어진 배열에서 가장 큰 연속구간합을 찾는 문제는 Kadane's algorithm을 이용해 간단히 해결할 수 있다.

 

예제 3에서 나와있듯이 "구간의 크기가 1 이상이어야한다는" 조건을 놓치지 말고 구현해주자.

 

아래는 제출한 소스코드이다:

#include <iostream>
using namespace std;

int N, total = 0, mn = 1000000007;
int arr[200000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	bool chk = 0;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		mn = min(mn, arr[i]);
	}
	for (int i = 0; i < N; i++) {
		int sgn; cin >> sgn;
		if (sgn) {
			total += arr[i];
			arr[i] *= -1;
		}
		else chk = 1;
	}

	if (chk == 0) {
		cout << total - mn;
	}
	else {
		int psum = 0, mx = 0;
		for (int i = 0; i < N; i++) {
			psum = max(psum + arr[i], 0);
			mx = max(mx, psum);
		}

		cout << total + mx;
	}
}