1-B-A 백준 16922번 로마숫자 만들기 (+ 로마숫자 만들기 2)

알고리즘 캠프에서 풀었던 다른 문제들:

알고리즘 캠프 인덱스

문제 링크:

16922번: 로마 숫자 만들기

16921번: 로마 숫자 만들기 2

N이라는 숫자를 분할하고 할당하는 경우의 수는 다음과 같다.

sum(IP(N,i) * C(4,i)), i=1 to min(N, 4)

IP(N,i)은 N을 i개로 분할하고 순서대로 나열하는 경우의 수, C(4,i)는 분할된 i개를 4개에 할당하는 경우의 수

IP(N,i)를 나열하면 조합꼴이 됨을 알 수 있다. =C(N-1,i) 따라서 식을 고쳐쓰면

sum(C(N-1,i) * C(4,i)), i=1 to min(N, 4)

 

하지만 해당 문제에서는 분할 간에 중복이 발생할 수 있다.

I	V	X	L
5			1
	1	5

위 두 할당의 경우 사용한 로마 digit 개수가 같고 로마 숫자 값도 동일하다. 뿐만아니라 여기에 동일한 조합의 로마 digit를 추가해도 역시 digit 개수와 숫자 값이 동일하다. 따라서 해당 중복을 제거해 주기 위해 높은 시간복잡도의 코드를 돌려서 결과값을 나열해본다.

 

중복을 제거한 분할의 경우의 수는 총 4개의 조합의 가감으로 이뤄져있는 것을 알 수 있다. 각 할당의 경우의 수에 i가 동일한 할당의 경우의 수 C(4,i)를 곱해서 로마 숫자의 개수를 구할 수 있다.

N	조합1	조합2	조합3	조합4
	C(4,1)+C(4,2)+...+C(4,4)     *        *            *	C(4,1)+C(4,2)+...+C(4,4)     *        *            *	C(4,1)+C(4,2)+...+C(4,4)     *        *            *	C(4,1)+C(4,2)+...+C(4,4)     *        *            *
1	C(1,1)
2	C(2,1)+C(2,2)
3	C(3,1)+C(3,2)+C(3,3)
4	C(4,1)+C(4,2)+...+C(4,4)
5	C(5,1)+C(5,2)+...+C(5,4)
6	C(6,1)+C(6,2)+...+C(6,4)	-1
7	C(7,1)+C(7,2)+...+C(7,4)	-C(1,1)->조합1(1)
8	C(8,1)+C(8,2)+...+C(8,4)	-C(2,1)-C(2,)->조합1(2)
9	C(9,1)+C(9,2)+...+C(9,4)	-조합1(3)	-C(2,1)-C(2,2)+2->-조합1(1)+2
10	C(10,1)+C(10,2)+...+C(10,4)	-조합1(4)	조합1(2)+3
13	C(5,1)+C(5,2)+...+C(5,4)	-조합1(7)	-조합1(5)+6
14	C(5,1)+C(5,2)+...+C(5,4)	-조합1(8)	-조합1(6)+7	+1
15	C(5,1)+C(5,2)+...+C(5,4)	-조합1(9)	-조합1(7)+8	+조합1(1)
	조합1(N)	-조합1(N-6)	-조합1(N-8)+N-7	+조합(N-14)
N, N -> C(4,i)를 곱하지 않고 결과에 더해진다.

조합1부터 조합4까지를 각각 크기 4의 배열로 나타내어 각각 DP로 조합을 유지해가면 시간 초과가 발생했다. 조합 2~4는 조합 1의 과거의 모습이기 때문에 조합 1을 계산하는 과정에서 구할 수 있게 되고, 해당 값들을 바로 답을 담은 변수인 a에 적용시키면 조합 배열 하나만 유지하면서도 정답을 구할 수 있다.

이를 코드로 구현하면 다음과 같고 시간복잡도는 O(N)이다.

#include <iostream>

using namespace std;

int N;
int coef[4] = { 4, 6, 4, 1 };
long long int var[4] = { 1 };

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;

	int h; long long int a = 0;
	// 1 ~ 6
	if (N <= 6) {
		for (h = 2; h <= N && h <= 6; ++h) {
			var[3] += var[2];
			var[2] += var[1];
			++var[1];
		}
		for (int i = 0; i < 4; ++i)
			a += coef[i] * var[i];
		if (N == 6)
			--a;

		cout << a;
		return 0;
	}
	// 7 ~ 8
	else if (N <= 8) {
		for (h = 2; h <= N - 6; ++h) {
			var[3] += var[2];
			var[2] += var[1];
			++var[1];
		}
		for (int i = 0; i < 4; ++i)
			a -= coef[i] * var[i];

		for (; h <= N; ++h) {
			var[3] += var[2];
			var[2] += var[1];
			++var[1];
		}
		for (int i = 0; i < 4; ++i)
			a += coef[i] * var[i];

		cout << a;
		return 0;
	}
	// 9 ~ 14
	else if (N <= 14) {
		for (h = 2; h <= N - 8; ++h) {
			var[3] += var[2];
			var[2] += var[1];
			++var[1];
		}
		a += N - 7;
		for (int i = 0; i < 4; ++i)
			a -= coef[i] * var[i];

		for (; h <= N - 6; ++h) {
			var[3] += var[2];
			var[2] += var[1];
			++var[1];
		}
		for (int i = 0; i < 4; ++i)
			a -= coef[i] * var[i];

		for (; h <= N; ++h) {
			var[3] += var[2];
			var[2] += var[1];
			++var[1];
		}
		for (int i = 0; i < 4; ++i)
			a += coef[i] * var[i];
		if (N == 14)
			++a;

		cout << a;
		return 0;
	}
	// 15 ~
	else {
		for (h = 2; h <= N - 14; ++h) {
			var[3] += var[2];
			var[2] += var[1];
			++var[1];
		}
		for (int i = 0; i < 4; ++i)
			a += coef[i] * var[i];

		for (; h <= N - 8; ++h) {
			var[3] += var[2];
			var[2] += var[1];
			++var[1];
		}
		a += N - 7;
		for (int i = 0; i < 4; ++i)
			a -= coef[i] * var[i];

		for (; h <= N - 6; ++h) {
			var[3] += var[2];
			var[2] += var[1];
			++var[1];
		}
		for (int i = 0; i < 4; ++i)
			a -= coef[i] * var[i];

		for (; h <= N; ++h) {
			var[3] += var[2];
			var[2] += var[1];
			++var[1];
		}
		for (int i = 0; i < 4; ++i)
			a += coef[i] * var[i];

		cout << a;
		return 0;
	}

	return 0;
}

---

BF를 적용하여 N을 네개의 로마 digit에 분할하면 O(N^4) 알고리즘을 구현할 수 있다.

#include <iostream>

using namespace std;

int N;
int RC[4] = { 1, 5, 10, 50 };
int RV[4];
bool s[1001];
int Rctr;

void BF(int d, int sum) {
	if (d == 4) {
		if (sum == N) {
			int R = 0;
			for (int i = 0; i < 4; ++i)
				R += RC[i] * RV[i];

			if (!s[R]) {
				s[R] = 1;
				++Rctr;
			}
		}
		return;
	}

	for (int i = 0; i <= N; ++i) {
		RV[d] = i;
		BF(d + 1, sum + i);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;

	BF(0, 0);

	cout << Rctr;

	return 0;
}