BOJ1970 건배(C++)

---

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

태그 : dp

---

사고 과정

O(N^2)
1자로 펴봐
dp[i][j] = i에서 j까지의 최대 쌍의 갯수

dp[i][j] = max(dp[i + 1][j - 1] + i와 j의 건배여부, dp[i][k] + dp[k + 1][j])

그런데 이 흐름으로 구현하면, 시간복잡도가 O(N^3)이 된다.

빅오 표기법의 허점? 이라고 볼 수 있는데, 러프하게 N^3이지만 2, 3번째 반복문의 범위가

각각 n - i, i이다. 식으로 보면 다음과 같다.

$\sum_{i=1}^{N-1} \sum_{j=1}^{N-i} i$ = $\sum_{i=1}^{N-1} i(N-i)$

자연수 거듭제곱 합 공식을 적용하면,

$\sum_{i=1}^{N-1} (Ni - i^2) = N\sum_{i=1}^{N-1} i - \sum_{i=1}^{N-1} i^2$ = $\approx N \left( \frac{N^2}{2} \right) - \frac{N^3}{3} = \frac{N^3}{2} - \frac{N^3}{3} = \frac{N^3}{6}$

N^3이지만, 10억 / 6은 1.6억이고 2초 시간 제한 내에 돌 수 있게 된다.

---

코드

#include <iostream>
using namespace std;

#define MOD 1000000007
typedef long long ll;

int n, arr[1001], ans;
int dp[1001][1001];

/*
*
*	O(N^2)
*	1자로 펴봐
*
*	dp[i][j] = i에서 j까지의 최대 쌍의 갯수
* 
* 
*/

void solve() {
	
	//i == size
	for (int i = 1; i < n; ++i) {
		for (int j = 1; j <= n - i; ++j) {
			dp[j][j + i] = dp[j + 1][j + i - 1] + (arr[j] == arr[j + i] ? 1 : 0);
			for (int k = j; k < j + i; ++k) {
				dp[j][j + i] = max(dp[j][j + i], dp[j][k] + dp[k + 1][j + i]);
			}
		}
	}
	ans = dp[1][n];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i];
	}

	solve();

	cout << ans;
}

---

후기

dp 테이블 짜는건 꽤 수월했으나,

시간초과에 대한 고민을 잘 해야하는 문제였다.

proof by ac했고 gemini로 명확하게 알게 되었다.