Codeforces Round #849 (Div. 4) - E번

문제는 여기...

https://codeforces.com/contest/1791/problem/E

Problem - E - Codeforces

 

 

울면서 시작..

 

빨간색 -> 내 원래 생각

초록색 -> 이렇게 생각해서 풀고 싶다

 

 

ai와 ai+1의 부호를 바꿔준다는 것이 결국

ai와 aj의 부호를 바꿔준다는 것과 같다는 것을 알아내는 게 이 문제의 포인트이다

(1 <= i, j <= N)

 

근데... 이 문제는 그거 말고도 0도 고려를 해줘야 한다

 

예제 2와 같은 입력

5
1 5 -5 0 2

에서는, -5와 0의 부호를 변환하면 -5도 양수가 될 수 있다.

 

그리고, 잘 생각을 해보면 위와 같은 역할을 하는 0은 단 하나만 있어도 된다

수열에 0이 하나 이상일 때, 마이너스인 원소의 개수가 홀수개여도 짝수개와 같은 역할을 해준다.

 

따라서,

1. 마이너스 원소 짝수개 -> 답 = abs 다 더한 sum

2. 마이너스 원소 홀수개

       2-1. 0 존재 -> 답 = abs 다 더한 sum

       2-2. 0 없음 -> 답 = abs 다 더한 sum + (절댓값이 가장 작은 minus값*2)

 

와 같이 생각해야 한다.

 

근데, 애초에 이렇게 풀 필요가 없다

"0이 있으면 마이너스의 원소가 홀수개여도 처리가 가능하다"

가 맞긴 하지만 이미 좀 복잡하다 ㅜ

 

잘 생각해 보면, 이 문제의 포인트는

마이너스의 개수가 홀수개이면 2개씩 양수로 바꿔주므로 마이너스가 하나는 무조건 남는다는 것이다

그리고 그 마이너스는 어디에도 붙여줄 수 있다.

 

sum을 가장 크게 하기 위해서는 마이너스가 abs가 가장 작은 값에 붙을 텐데,

1. 0이 없는 수열에서는 어떠한 값 A에 붙을 것이고,

2. 0이 있는 수열에는 0에 붙을 것이다.

 

따라서

1. 번 케이스에서는 (abs 다 더한 sum) - 2*A

2. 번 케이스에서는 (abs 다 더한 sum) - 2*0

 

이 된다.

 

그리고 2번 케이스는 내가 위에서 말했던

0이 있다면 마이너스 원소의 개수가 홀수더라도 모두 0 이상으로 만들어 줄 수 있다(모든 마이너스들을 +로 만들어 줄 수 있다)에 해당한다

 

ㅜ 이렇게 쉽게 생각하면 편할 텐데~~~~

참...

아쉽다

잘하고 싶은데!

 

내가 푼 방식으로도 풀리긴 풀린다 실제로 코드도 엄청나게 복잡해진 건 아니고..

그래도 위와 같이 좀 더 편하게 풀고 싶어서 기록해 놓는다.

 

(AC 받은 코드)

#include <iostream>
#include <algorithm>
using namespace std;

int arr[200000];

int main() {
	int TC;
	scanf("%d", &TC);
	while (TC--) {
		int N;
		scanf("%d", &N);
		int minus_cnt = 0;
		int min_abs = 2000000000;
		bool has_zero = false;
		long long ans = 0;
		for (int i = 0; i < N; i++) {
			scanf("%d", &arr[i]);
			ans += abs(arr[i]);
			min_abs = min(min_abs, abs(arr[i]));
			if (arr[i] < 0) {
				minus_cnt++;
			}
			else if (arr[i] == 0) has_zero = true;
		}
		if ((minus_cnt&1) && !has_zero) {
			ans -= (min_abs*2);
		}
		printf("%lld\n", ans);
	}
}