[BOJ] 백준 3037. 혼란 (Gold I)

포스팅하기 귀찮아서 안하려다가,

대부분의 풀이 코드가 바텀업이어서 나같은 탑다운 고집러들을 위해 포스팅하려 한다.

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

3037번: 혼란

문제 요약을 하자면, 1부터 N까지 이루어진 수열이 있는데, 오름차순이 아닌 총 순서쌍의 개수를 '혼란도' 라고 한다. N<=1,000, 혼란도<=10,000이 주어질 때, 이러한 수열은 총 몇 개 있는지 구하는 것이다.

---

의식의 흐름 및 해설

처음에는 '버블 소트' 문제가 생각나 세그먼트 트리로 해결하는 문제인 줄 알았다. 그런데, 이 문제는 혼란도를 0으로 만들기 위해 몇 번 swap해야 하는지 구하는 문제가 아닌, 이미 swap개수는 주어져 있고 이러한 수열이 총 몇 개인지를 구하는 문제였기 때문에 아예 다르게 접근해야 했다.

 

처음엔 dp[N][C]에 따른 점화식을 세워보려 하였다. 

나는 점화식을 세울 때 임의의 예제를 만들어서 세워보는 편이다.

예를 들어 [4 1 2 3]과 같은 수열이 있다고 할 때,

이전항은 최대 N이 3이므로 [1 2 3]에다가 4를 집어넣어보면서 점화식을 세워보려 했는데 생각보다 잘 되지 않았다.

 

그래서 내 머릿속 시뮬레이션으로 점화식을 세우기엔 좀 어려운 문제다 싶어, 첫째항부터 한 번 나열해보았다.

 

N이 증가할수록 혼란도가 증가하는 규칙이 보인다.

N이 1일 때, 혼란도는 0이 최대,

N이 2일 때, 혼란도는 0+(0~1),

N이 3일 때, 혼란도는 0+(0~2), 1+(0~2)

N이 4일 때, 혼란도는 0+(0~3), 1+(0~3), 2+(0~3), ..., +3+(0~3) 임을 알 수 있다.

 

따라서 N일 때 혼란도는 N-1일 때 나온 혼란도들에게 0~N-1까지 더한 혼란도들이 추가로 발생함을 알 수 있다.

즉, 점화식은 아래 식과 같다.

 

여기까지 제대로 하면 정답이다. 그런데, 이 점화식 그대로 제출하면 시간초과가 날 것이다.

여기서부턴 시행착오란에 서술하겠다.

---

시행착오

위 점화식대로 코드를 짜면 아래 dp코드가 나올 것이다.

const int MAX = 1001;
const int MAXC = 10001;
const int MOD = 1e9 + 7;
int N, C, d[MAX][MAXC];
int dp(int cur, int c) {
	if (cur == 1)
		return !c ? 1 : 0;
	int& ret = d[cur][c];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = 0; i < cur; i++) {
		if (c - i >= 0) {
			ret += dp(cur - 1, c - i);
			ret %= MOD;
		}
	}
	return ret % MOD;
}

이 코드의 시간복잡도는, 우선 dp함수의 시간복잡도가 O(N)이다. 

for문으로 N번마다 dp함수를 재귀적으로 실행하는데다가, 재귀의 수명은 최대 N이므로 dp함수의 총 시간복잡도는 대략 O(N^3)이 나온다. 사실 정확한 식인진 모르겠다. O(N^2C)일 수도 있는데, 확실한 것은 dp식 내에 for문이 있으므로 세제곱꼴 시간복잡도라는 것이다.

위 코드대로라면 당연히 7%에서 시간초과가 날 것이다.

 

그런데 생각해보면, 위 점화식은 아래식으로 바꿀 수 있음을 알 수 있다.

짜잔~~

???? 아니 이게 무슨소리일까.

 

자, 예시를 들어 설명해보자.

dp[4][5]=dp[3][2]+dp[3][3]+dp[3][4]+dp[3][5]임은 시간초과 나는 점화식으로 알 수 있다.그

그리고 dp[4][4]의 값은 dp[3][1]+dp[3][2]+dp[3][3]+dp[3][4]이다. 위 점화식과 겹치는 부분을 진하게 칠해보았다.

 

이제 슬슬 보이는가? dp[4][5]=dp[4][4]+dp[3][5]-dp[3][1]을 하면, dp[3][1]+...+dp[3][5]-dp[3][1]로 바꿀 수 있는 것이다. 즉, 연속된 배열의 합이므로 누적합 성질을 이용하면 된다는 점이다!

 

따라서 코드를 아래와 같이 바꿀 수 있다.

int N, C, d[MAX][MAXC];
int dp(int cur, int c) {
	if (!c)
		return 1;
	if (cur == 1)
		return !c ? 1 : 0;
	int& ret = d[cur][c];
	if (ret != -1)
		return ret;
	ret = 0;
	ret += dp(cur, c - 1) + dp(cur - 1, c);
	ret %= MOD;
	if (c >= cur)
		ret -= dp(cur - 1, c - cur);
	ret = (ret + MOD) % MOD;
	return ret % MOD;
}

dp 식이 총 3번 일어나며, dp함수의 시간복잡도는 O(C)이므로 O(3*N*C)임을 알 수 있다. 이는 충분히 1초 내에 돌아가는 코드이다.

여기서 시간복잡도를 조금이라도 줄이려면, 불가능하거나 수열의 개수가 0일 때의 조건들을 미리 체크해 바로바로 리턴해주게 하면 된다. 예를 들어, N일 때 C의 값은 최대 N(N-1)/2 를 초과할 수 없다는 점. 이 점을 이용하면 시간복잡도가 조금이나마 줄어든다.

나보다 빠른 탑다운 코드도 존재했었다. 그러나 대부분의 풀이는 바텀업이었다.

아무래도 누적합을 이용하여 전처리를 할 때 바텀업이 훨씬 편하므로 그럴 수 밖에 없다고 생각했다.

바텀업 코드는 약 80ms 정도의 속도를 지니는 듯 했다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 1001;
const int MAXC = 10001;
const int MOD = 1e9 + 7;
int N, C, d[MAX][MAXC];
int dp(int cur, int c) {
	if (cur * (cur - 1) / 2 < c)
		return 0;
	if (!c)
		return 1;
	if (cur == 1)
		return !c ? 1 : 0;
	int& ret = d[cur][c];
	if (ret != -1)
		return ret;
	ret = 0;
	ret += dp(cur, c - 1) + dp(cur - 1, c);
	ret %= MOD;
	if (c >= cur)
		ret -= dp(cur - 1, c - cur);
	ret = (ret + MOD) % MOD;
	return ret % MOD;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> C;
	memset(d, -1, sizeof(d));
	cout << dp(N, C) << "\n";
}

---

누적합을 이용하여 dp 점화식을 바꿔버린다는 점이 신선하게 다가왔다.

앞으로 연속된 배열일 때, 그리고 연속되게 겹치는 점이 많을 때 누적합으로 시간복잡도를 줄여보는 아이디어를 생각해볼 수 있게 많이 수련을 해야겠다.

 

이 문제에 대한 탑다운 포스팅이 찾아보면 나올지 모르겠지만, 내 생각엔 아마 이 문제를 탑다운으로 해결하는 풀이를 쓴 포스팅은 내가 최초이지 않까 싶다.

아니면 뭐...어쩔수 없지만 ㅎ..