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

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

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

10803번: 정사각형 만들기

 

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

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

 

 

C++ 소스코드)

 

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