[BAE/<JOON> 문제풀이] 4457. 상근이의 자물쇠

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

4457번: 상근이의 자물쇠

서론

구현 거지같이해서 무한 맞왜틀했는데 알고리즘 톡방에서 고수분(개잘함)에게 코드 리뷰받고 풀었다. 감사합니다. ㅠㅠ

잘하는 사람들 코드보고 반례찾는거보면 진짜 신기하다. 심지어 내가 맞다고 확신한 부분에서 틀렸는데도 끝까지 전수검사해서 찾아주심. 

https://anz1217.tistory.com/ <= 고수분 블로그

 

+ 웃긴게 계산 로직이 틀렸음에도 21항 값이 맞게 나와서 더 못찾았다. 마성의 테스트 케이스;

---

풀이

서론에서 호들갑을 떨어놨지만 사실 풀이 원리는 간단하다. 주어진 조건이 2가지 ( : 트리 높이 / 노드 개수 ) 이므로 DP로 해결할 수 있다. 새로 추가되는 루트 노드를 제외한 나머지 노드를 양쪽에 배분하는 방식으로 풀었다.

즉, 현재 계산하려는 노드 수 i 에 대해서 (i - 1)이 루트 노드를 제외한 노드 수가 되고 이 노드를 양쪽 서브 트리에 배분해야하니 0~(i-1)/2 까지 순회하며 그 값만큼 양쪽에 노드 개수를 배분하고, 배분된 노드로 만들 수 있는 모든 높이 k에 대해 반대쪽 노드에서 k + 1, k, k - 1 높이가 가능하다면 그 경우의 수들을 각각 곱해 더한다. 양쪽 서브트리의 노드 수나 노드 높이가 서로 다른 경우, 양쪽 노드구조가 바뀌면 중복되는 트리구조가 하나 더 생기므로 * 2를 해줘야 한다. 두 개가 모두 같으면 당연히 바꿔도 구조가 같으므로 * 2를 할 필요가 없다. 

점화식은 다음과 같다.

DP[i][j] = 노드 개수가 i이고 높이가 j인 트리 개수

DP[i][j] = SUM(DP[0~(i - 1)/2:j][0~21:k] * DP[i - j -1][k + 1, k, k - 1]

※ 0~21은 노드 최대 높이를 넉넉하게 계산한 값이다.

 

고수분이 찾아주신 틀렸던 부분은 2가지였다.

1. 트리의 최대 높이를 ceil(log2(1427 + 1)) 로 설정했는데, 트리가 불균형한 경우 이 높이를 초과할 수 있다. 최대 높이는 계산이 불가능해서 넉넉하게 높이 배열 사이즈 * 2했다.

2. 양쪽 서브트리의 노드 수가 같은 경우, k - 1 과 k + 1 을 모두 검사하면 같은 경우를 2번 세게 된다. 별도의 설명이 필요 없을 만큼 자명하다.

 

사이즈 계산을 정교하게 하면 좀 더 빠른 코드를 짤 수 있지만 이미 AC 맞았고 그 시간에 다른 문제 더 푸는게 나을 것 같다.

---

코드

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
const ll mod = 1e9;
int main()
{
	//ios::sync_with_stdio(0); cin.tie(0);		
	int n = 1427; vector<vector<ll>> dp(n + 1, vector<ll>(ceil(log2(n + 1)) * 2 + 3)); // dp[i][j] = 노드 수 i에 높이 j 인 트리 개수
	dp[0][0] = 1;
	dp[1][1] = 1;
	//dp[2][2] = 2;	
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= (i - 1) / 2; j++) {
			//for (int k = (int)ceil(log2(j + 1)); k <= (int)ceil(log2(n + 1)); k++) {
			for (int k = 0; k <= (int)ceil(log2(n + 1)) * 2; k++) {
				for (int l = -1; l <= 1; l++) {		
					if (k + l < 0 || (l == -1 && j == i - j - 1)) continue;
					ll s = dp[j][k] * dp[i - j - 1][k + l]; s %= mod; // 노드 개수가 i인 트리의 양쪽 서브 트리의 합은 (i - 1). 높이차 1 이하 3 경우 검사
					if (!(j == i - j - 1 && l == 0)) {// 양쪽 서브 트리의 높이와 노드수가 같다면 순서만 바꾸면 중복이 생기므로 중복 제거.
						s += s;
						s %= mod;
					}					
					int h = k > k + l ? k : k + l; // 양쪽 서브 트리중 높은 쪽의 높이 + 1이 최종 높이
					dp[i][h + 1] += s;		
					dp[i][h + 1] %= mod;
				}
			}
		}
	}
	while (cin >> n) {
		ll sum = 0;
		for (int i = 0; i <= ceil(log2(1428)) * 2; i++) {
			sum += dp[n][i]; sum %= mod;
		}
		printf("%09lld\n", sum % mod);
	}
	return 0;
}