백준 21757 / C++

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

21757번: 나누기

 

[ 풀이 ] 

dp[i][j]를 i번째 인덱스까지 j개로 분할하는 방법의 수라고 놓자.

상태전이 시켜보자. i번을 안쓰는 경우 그냥 dp[i+1][j]로 넘어간다. 

i번을 사용하는 경우 dp[i+1][j+1]로 넘어간다. 사용할 수 있는 경우는 문제조건에 따라 잘 체크하면 된다. 

그리고 매번 i번에서 i+1만 참조하므로 토글링으로 공간복잡도를 조금 줄여줄 수 있다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, x, psum[100001], dp[2][4];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		psum[i] = psum[i - 1] + x;
	}
	if (psum[n] % 4) {
		cout << 0 << '\n';
		return 0;
	}
	dp[0][0] = 1;
	ll s = psum[n] / 4;

	// dp[i][j]=dp[i-1][j]+(i번 사용이 가능하다면)dp[i-1][j-1]
	for (ll i = 1; i <= n; i++) {
		dp[i % 2][0] = 1;
		for (ll j = 1; j <= 3; j++) {
			dp[i % 2][j] = dp[(i - 1) % 2][j];
			if (psum[i] == j * s) dp[i % 2][j] += dp[(i - 1) % 2][j - 1];
		}
	}
	cout << dp[(n - 1) % 2][3] << '\n';
}