[백준 1437번] 수 분해 (C++)

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

풀이가 2가지가 있다.

1. Dp

2. 수학

---

1. 다이나믹 프로그래밍

Dp로 풀려고 하면 당연히 점화식을 찾아야 하고 노가다를 하다보면 점화식이 쉽게 찾아진다.

n > 4인 경우에서 dp[n] = dp[n-3]*3이 된다.

 

#include <iostream>
#define mod 10007
using namespace std;

int main() {
	int n;
	cin >> n;
	int* arr = new int[n+1];
	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 3;
	arr[4] = 4;
	for(int i = 5; i <= n; i++){
		arr[i] = (arr[i-3] * 3) % mod;
	}
	cout << arr[n];
}

 

2. 수학

수학적 접근이 쉽지 않은데... 결론적으로는 3을 가장 많이 만들면 된다.

DP로 접근할때 노가다한 수들을 소인수 분해 해보면 전부다 2와3으로 표현될 수 있으며, 3이 최대로 들어가고 부족한 경우 2를 사용했다. (단, 10 = 3+3+3+1과 같이 1이 등장하는 경우는 3을 하나 지우고 2²을 넣어주면 된다)

 

3을 최대로 많이 사용하는건 n의 n제곱근의 최댓값을 구해보면 된다.(미분해서 = 0 으로 극댓값 찾으면 됨.)

그러면 최댓값을 만드는 n이 자연상수 e가 된다. 따라서 e(2.718xx..)에 가까운 3이 자연수 중에서 가장 커지게 하는 값이다. (사실 가깝다고 하면 안되고 함수를 그려보면 f(2) < f(3)이며 e에서 극댓값을 가진다.)

따라서 3을 최대로 쓰고 나머지를 2로 채우면 수를 구성하는 수들의 곱이 최대가 된다.

 

사실상 문제를 풀면서 제대로 된 증명을 하기엔 어렵고 관찰해서 발견하는게 낫다.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	if(n == 0 || n == 1) {
		cout << n;
		return 0;
	}
	int mx, re, ans;
	mx = n/3;re = n%3;
	ans = 1;
	if(re == 2) ans *= 2;
	else if(re == 1) {
		ans *= 4;
		mx -= 1;
	}
	
	for(int i = 0; i < mx; i++){
		ans *= 3;
		ans %= 10007;
	}
	cout << ans;
}