[CodeForce 327A] Fliping Game C++ 풀이 - Maximum SubArray로 풀기

1. 문제

---

2. 문제 분석

https://codeforces.com/problemset/problem/327/A

Problem - 327A - Codeforces

 

이 문제를 풀기 전, Maximum SubArray에 대해 먼저 살펴보자.

생각하기 어려운 부분이지만, 배우고 나면 간단한 풀이이다.

 

 ✔ 먼저 정리할 점

🎯
전체 Array에 대해 SubArray의 size가 0도 될까?

🔊
문제에 주어진 조건에 따라 0도 되면 되고, 최소 1이상이면 그거에 맞게 풀면 된다.

🎯
size가 0인 배열의 합은 0임은 자명하다. 그럼 size가 0인 배열의 곱은 0일까?

🔊
size가 0인 배열의 곱은 1이다. 그게 자연스러움. 생각해보면, size가 0인 것에 곱이 무엇이든 간에, size가 1이 되면 그 수의 값이 곧 그 배열의 곱이 되기 때문이다.

🏆 Maximum SubArray는 배열이 있고, 양수 음수 다 있는 경우에만 의미가 있다.
그럼 그 중에서 일부를 골라서, Sum이 최대가 되도록 하는 문제.

 

그럼 우리는 각 칸에 대해, 그 자리에서 끝나는 가장 큰 합을 계산할 것이다.

내가 2번째 칸에 대해, 그 자리에서 끝나는 가장 큰 합을 계산하려 한다면,

 

size가 0인걸 허용하면 size가 0인 것,

2번째 자리만 취해서 size가 1인 것,

2, 1번째 자리를 취해서 size가 2인 것, ... 이런 식으로.

---

0, 1번째 자리의 index의 Maximum SubArray를 구하는 과정.

---

2번째 자리의 index의 Maximum SubArray를 구하는 과정.

 

---

 

그럼, 내가 5번째 칸에서 끝나는 것 중 가장 큰 값을 x라 하면,
그 다음 칸에는 무엇을 쓸 수 있을까?

🔊
일단 x는 size가 0~5인 것을 다 봐서, 제일 큰 것을 적은거니까,
6번째 칸에도 이를 똑같이 한다면, size가 0~6인걸 다 봐서, 제일 큰 것을 적을 텐데
이미 앞서 5번째 칸에서 size가 0인거에 6번째 칸을 더하면, 6번째 칸 기준 size가 1인 것과 같다.

 

그럼 제일 큰 것도 똑같다. (x + 6번째 칸의 값)이다.

 

단, 여기서 한 가지 빠진 가정은, 6번째 자리에서 size가 0인 것.

(x + 6번째 칸의 값)은 size 1~6을 고려한 것이기 때문이다.

그래서 이 둘 중에서 큰게 6번째 칸의 답이다.

 

6번째 칸의 값을 a라 하면, M[6] = max(x+a, 0)

 

---

3. 풀이

문제로 돌아오자.

 

문제에서 주어진 move를 하게 되면 1은 0이 되고, 0은 1이 된다.

그럼 전체 합의 측면에선, 원래 더해지려던 1이 0이 되어 더해지지 않으므로 총 -1 손해이고,

더해지지 않던 0이 1이 되어 더해지므로 총 1 이득이다.

 

그래서, 1은 -1, 0은 1로 바꿔서 풀어보자.

 

i~j를 뒤집는다고 해보자.

이 문제는 j가 i이상이었으니, 1칸은 뒤집어야 한다. 즉, size 0을 허용하지 않는다.

---

4. 코드

---

아래는 정답 코드

#include <iostream>

using namespace std;

int main()
{
	// A : 1 => -1, 0 => 1로 바꾼 배열.
	// B : 원래 받은 값들.
	// S : Maximum SubArray가 시작된 지점.
	// M : i번째 위치에서 가장 큰 Maximum SubArray값.
	int n, A[101], B[101], S[101], M[101];

	cin >> n;	

	for (int i = 0; i < n; i++)
	{
		cin >> B[i];
		if (B[i] == 1) A[i] = -1;
		else A[i] = 1;
	}	

	M[0] = A[0]; S[0] = 0;

	for (int i = 1; i < n; i++)
	{
		if (M[i - 1] + A[i] > A[i])
		{
			M[i] = M[i - 1] + A[i];
			S[i] = S[i - 1];
		}
		else
		{
			M[i] = A[i];
			S[i] = i;
		}
	}

	int maxLen = -1;	
	for (int i = 0; i < n; i++)
	{
		maxLen = max(M[i], maxLen);
	}

	int index = 0;
	for (int i = 0; i < n; i++)
	{
		if(M[i] == maxLen)
		{
			index = i;
		}
	}

	if (n == 1)
		cout << 1 - B[0];
	else
	{
		int ans = 0;
		for (int i = S[index]; i <= index; i++)
		{			
			B[i] = 1 - B[i];
		}				

		for (int i = 0; i < n; i++)
			ans += B[i];

		cout << ans;
	}
}

 

<추가 배운점 정리>

- exactly : 한번 꼭 하라는 의미 ("at least"는 안해도 됨.)

- Maximum SubArray는 Prefix Sum보다 더 간단하다.