c언어 25634번 전구 상태 뒤집기 (백준)

#include <stdio.h>

int main(void)
{
	int n;
	scanf("%d", &n);
	
	int arr[n];
	for(int i=0; i<n; i++) scanf("%d", &arr[i]);
	
	int one=0, zero=0, max = -1e9, tmp;
	for(int i=0; i<n; i++)
	{
		scanf("%d", &tmp);
		if(tmp) {
			one += arr[i];
			zero -= arr[i];	
			if(max < -1*arr[i]) max = -1*arr[i];
		} else {
			zero += arr[i];
			if(zero < arr[i]) zero = arr[i];
			if(max < zero) max = zero;
		}
	}
	printf("%d", one+max);
}

풀이 : dp

 

변수 설명

one : 켜져있는 전구들의 가치의 합

zero : 켜져있는 전구들의 경우 가치 * -1 을 누적, 꺼져있는 전구들의 경우 가치 를 누적

          단 여러 전구의 가치를 누적 한 것보다, 단 하나의 전구의 가치가 더 큰 경우 이걸로 변경한다.

max : 하나 이상의 전구를 변환할 때 얻을 수 있는 가장 큰 값

          전구가 다 켜져있는 경우를 대비해서, 전구들 중 가장 가치가 작은 것을 max에 대입해야 하며,

          꺼져 있는 전구를 다룰 때는, zero 가 max보다 크면 max에 zero을 대입해 주면 됩니다.

 

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

25634번: 전구 상태 뒤집기