[백준] 10803번 정사각형 만들기 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법 - 정사각형 만들기

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

10803번: 정사각형 만들기

 

쉬운 DP문제일 줄 알았으나, TLE에서 최적화하느라 꽤 걸린 문제였습니다. 

(i)의 방법으로 1~n/2, 1~m/2까지 자릅니다. 하지만 큰 수에서 O(n*m)의 연산이 필요하기 때문에 큰 수에서는 (ii) 방법을 이용하여 최소 정사각형 개수를 구합니다.

 

 

C++ 소스코드)

	int solve(int n, int m) {
	if (n % m == 0) return n / m;
	if (n == m) return 1;
	int& ret = cache[n][m];
	if (ret != -1) return ret;
	// 정사각형 최대 개수
	ret = n * m;
	if(n >= 3 * m)
	ret = min(ret, solve(n - m, m) + 1);
	else {
	for (int i = 1; i <= n / 2; ++i)
	ret = min(ret, solve(n - i, m) + solve(i, m));
	for (int j = 1; j <= m / 2; ++j)
	ret = min(ret, solve(n, m - j) + solve(n, j));
	}
	return ret;
	}

view raw 10803.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/10803_%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions