[백준/C++] 동작 그만. 밑장 빼기냐? (No.20159)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 밑장을 뺄 경우 어떻게 수가 분배 되는지를 파악하면 누적합을 이용해 쉽게 풀 수 있는 문제다.

 

그림을 통해 한번 알아보자

 

img1

 

B카드를 받아야 하는 상태에서 밑장을 빼면, A카드를 받고 그 뒤에 z, b, c, d ...카드를 받게 된다.

즉, 내가 카드를 받을 순서에서 밑장을 빼면 그때부터 나는 원래 받을 카드가 아니라, 상대방의 카드를 전부 받게 된다.

 

이를 이용하면 내가 받을 i번째 카드의 밑장을 빼면 내가 원래 받을 i-1번째 카드까지의 합 + 상대방이 받을 i번째 카드부터 N/2번째 카드까지의 합으로 나타낼 수 있다. 

 

이때, 상대방의 차례에 밑장을 빼면 경우가 약간 다르다 

 

img2

 

그림에서 보다시피 상대방의 차례에서 밑장을 빼면 밑장은 상대가 받게 되고 상대방이 받을 카드를 내가 받게 된다.

그대로 카드를 받고나면 상대방의 밑장을 뺀 나머지 카드를 받는다는 사실을 알 수 있다.

 

이를 정리하면 상대방의 i번째 카드의 밑장을 빼게 되면, 내가 받을 i번째 카드까지의 합 + 상대방의 i번째 카드부터 N/2-1번째 카드까지의 합으로 나타낼 수 있다.

 

 

이제 위 두 경우를 누적합을 이용해 계산하면 빠르게 문제를 해결할 수 있다. 

 

 

​

[아이디어 정리]

1. 상대방이 받는 카드와 내가 받는 카드를 누적합을 이용해 계산해 둔다.
2. 내 차례에서 밑장을 빼는 경우와 상대방의 차례에서 밑장을 빼는 경우를 구분해 최대값을 구한다.
3. 구한 최대값을 출력한다.

 

 

 

Code

 

 

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin >> N;
	int num;
	vector<int> odd(1+(N / 2), 0);
	vector<int> even(1+(N / 2), 0);
	for (int i = 1; i <= N/2; i ++) {
		cin >> num;
		odd[i] = odd[i-1]+num;
		cin >> num;
		even[i] = even[i - 1] + num;
	}
	int A=even[N/2];
	for (int i = 1; i <= N/2; i++) {
		
		A = max({ odd[i] + even[N / 2] - even[i], odd[i] + even[N / 2] - even[i-1] - num, A});
	}
	cout<<A;
	return 0;
}

---

 

처음에 상대방의 차례에 밑장을 빼는 경우나 내 차례에 밑장을 빼는 경우가 같은 줄 알고 풀어서 틀렸다

잘 생각해보니 상대방의 차례에 밑장을 빼면 다른 경우가 생겨서 이를 고려해 바로 풀 수 있었다.

문제를 풀 때 잘 생각해보고 한번에 풀 수 있는 연습을 해보자...

 

 

 

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