최소 정사각형 수로 자른 종이
직사각형 크기의 종이가 주어지면 axb . 과제는 종이 전체를 잘라내는 것입니다. 최저한의 수 정사각형 조각. 어떤 크기의 정사각형 조각도 선택할 수 있지만 잘라야 합니다. 겹치거나 여분의 공간을 남기지 않고 .
예:
입력: 가 = 5 ㄴ = 8
5 X 8 크기의 종이에서 잘라낸 정사각형 5개
산출: 5
설명: 종이를 5개의 정사각형으로자를 수 있습니다. 5x5 크기의 정사각형 1개, 3x3 크기의 정사각형 1개, 2x2 크기의 정사각형 1개 및 1x1 크기의 정사각형 2개.입력: 가 = 13 ㄴ = 11
13 X 11 크기의 종이에서 잘라낸 정사각형 6개
산출: 6
설명: 종이를 6개의 정사각형으로자를 수 있습니다. 7x7 크기의 정사각형 1개 6x6 크기의 정사각형 1개 5x5 크기의 정사각형 1개 4x4 크기의 정사각형 2개 및 1x1 크기의 정사각형 1개.입력: 가 = 6 ㄴ = 7
6 X 7 크기의 종이에서 잘라낸 정사각형 5개
산출: 5
설명: 종이를 5개의 정사각형으로자를 수 있습니다. 4x4 크기의 정사각형 1개, 3x3 크기의 정사각형 2개, 3x3 크기의 정사각형 2개입니다.
5 X 8 크기의 종이에서 잘라낸 정사각형 5개 
13 X 11 크기의 종이에서 잘라낸 정사각형 6개 
6 X 7 크기의 종이에서 잘라낸 정사각형 5개 목차
[잘못된 접근법 1] 탐욕스러운 기법 사용
첫눈에는 먼저 종이에서 가능한 가장 큰 정사각형을 자르고 나머지 종이에서 가장 큰 정사각형을 자르는 식으로 종이 전체를 자르면 문제가 쉽게 해결될 수 있는 것처럼 보일 수 있습니다. 그러나 이 해결책은 올바르지 않습니다.
욕심 많은 접근 방식이 작동하지 않는 이유는 무엇입니까?
크기가 큰 종이를 고려하십시오. 6x7 그러면 우리가 탐욕스럽게 종이를 자르려고 하면, 7 사각형: 1 크기의 제곱 6x6 그리고 6칸 크기 1x1 올바른 해결책은 다음과 같습니다. 5. 따라서 탐욕스러운 접근 방식은 작동하지 않습니다.
[잘못된 접근 방식 2] 동적 프로그래밍 사용
동적 프로그래밍 수직 또는 수평 절단: 올바른 것처럼 보이는 또 다른 솔루션은 다음을 사용하는 것입니다. 동적 프로그래밍 . 우리는 다음과 같이 dp[][] 테이블을 유지할 수 있습니다. dp[i][j] = 해당 크기의 종이에서 잘라낼 수 있는 최소 정사각형 수 나는 x j . 그런 다음 크기의 용지에 대해 도끼
- 각 행을 따라 잘라볼 수 있습니다. dp[i][j] = min(dp[i][j] 1 + dp[i - k][j] + dp[k][j]) 여기서 k는 [1 i - 1] 범위에 있을 수 있습니다.
- 각 열을 따라 잘라볼 수 있습니다. dp[i][j] = min(dp[i][j] 1 + dp[i][j - k] + dp[i][k]) 여기서 k는 [1 j - 1] 범위에 있을 수 있습니다.
마지막으로 최소한의 모든 상처가 답이 될 것입니다. 하지만 이 해결책 역시 올바르지 않습니다.
동적 프로그래밍 접근 방식을 사용하여 수직 또는 수평 절단이 작동하지 않는 이유는 무엇입니까?
수직 또는 수평 절단이 항상 직사각형을 두 부분으로 나눌 것이라고 가정하기 때문에 이것은 작동하지 않습니다. 크기가 큰 종이를 고려하십시오. 13x11 그런 다음 DP 접근 방식을 사용하여 종이를 자르려고 하면 8개의 정사각형을 얻게 되지만 정답(예제에 표시된 대로)은 6입니다. 따라서 동적 프로그래밍은 작동하지 않습니다.
[올바른 접근 방식] DFS 및 동적 프로그래밍 사용
C++그만큼 아이디어 사용하여 종이 전체를 자르는 것입니다 DFS ~에 상향식 방법. 모든 단계에서 종이의 가장 왼쪽 모서리를 찾아 그 모서리에서 가능한 모든 크기의 정사각형을 잘라보세요. 정사각형을 다시 자른 후 남은 용지의 왼쪽 가장 낮은 모서리를 찾아 가능한 모든 크기의 정사각형을 자르는 등의 작업을 수행합니다. 그러나 가능한 모든 용지 크기의 왼쪽 아래 모서리에서 가능한 모든 절단을 시도한다면 이는 매우 비효율적입니다. 다음을 사용하여 최적화할 수 있습니다. 동적 프로그래밍 가능한 각 용지 크기에 대한 최소 절단량을 저장합니다.
모든 용지 크기를 고유하게 식별하기 위해 remSq[i]가 용지의 i번째 열에 1x1 크기의 나머지 정사각형 수를 저장하도록 remSq[] 배열을 유지할 수 있습니다. 따라서 크기가 6x7인 용지의 경우 remSq[] = {6 6 6 6 6 6 6}입니다. 또한 가장 왼쪽 모서리를 찾기 위해 최대 남은 사각형을 가진 첫 번째 인덱스를 찾습니다. 따라서 remSq[] 배열의 값을 해시하여 remSq[] 배열의 가능한 모든 값에 대한 고유 키를 찾을 수 있습니다.
// C++ Program to find minimum number of squares to cut // from a paper of size axb #include using namespace std ; // function to get the hash key for remSq array int getKey ( vector < int > & remSq int b ) { int base = 1 ; int key = 0 ; for ( int i = 0 ; i < b ; i ++ ) { key += ( remSq [ i ] * base ); base = base * ( b + 1 ); } return key ; } // Recursive function to find the minimum number of square cuts // for a given remSq array int minCutUtil ( vector < int > & remSq int a int b map < int int > & memo ) { // pointers to mark the start and end of range // with maximum remaining squares int start end ; // Check if we have previously calculated the answer // for the same state int key = getKey ( remSq b ); if ( memo . find ( key ) != memo . end ()) return memo [ key ]; int maxRemSq = 0 ; // Find the starting point of min height for ( int i = 0 ; i < b ; i ++ ) { if ( remSq [ i ] > maxRemSq ) { maxRemSq = remSq [ i ]; start = i ; } } // If max remaining squares = 0 then we have already // cut the entire paper if ( maxRemSq == 0 ) return 0 ; end = start ; vector < int > newRemSq = remSq ; int ans = INT_MAX ; // Find the ending point of min height while ( end < b ) { // length of edge of square from start till current end int squareEdge = end - start + 1 ; // If the current column does not have maximum remaining // squares or if it's impossible to cut a square of // size squareEdge then break out of the loop if ( newRemSq [ end ] != maxRemSq || newRemSq [ end ] - squareEdge < 0 ) break ; // If we can cut a square of size squareEdge // update the remainingSquares for ( int i = start ; i <= end ; i ++ ) newRemSq [ i ] = maxRemSq - squareEdge ; // Find the solution for new remainingSquares ans = min ( ans 1 + minCutUtil ( newRemSq a b memo )); end += 1 ; } return memo [ key ] = ans ; } // Function to find the minimum number of squares we can cut // using paper of size a X b int minCut ( int a int b ) { // if the given rectangle is a square if ( a == b ) return 1 ; // Initialize remaining squares = a for all the b columns vector < int > remSq ( b a ); map < int int > memo ; return minCutUtil ( remSq a b memo ); } int main () { // Sample Input int a = 13 b = 11 ; // Function call to get minimum number // of squares for axb cout < < minCut ( a b ); return 0 ; }
Java // Java Program to find minimum number of squares to cut // from a paper of size axb import java.util.* ; class GfG { // function to get the hash key for remSq array static int getKey ( int [] remSq int b ) { int base = 1 ; int key = 0 ; for ( int i = 0 ; i < b ; i ++ ) { key += ( remSq [ i ] * base ); base = base * ( b + 1 ); } return key ; } // Recursive function to find the minimum number of square cuts // for a given remSq array static int minCutUtil ( int [] remSq int a int b Map < Integer Integer > memo ) { // pointers to mark the start and end of range // with maximum remaining squares int start = 0 end ; // Check if we have previously calculated the answer // for the same state int key = getKey ( remSq b ); if ( memo . containsKey ( key )) return memo . get ( key ); int maxRemSq = 0 ; // Find the starting point of min height for ( int i = 0 ; i < b ; i ++ ) { if ( remSq [ i ] > maxRemSq ) { maxRemSq = remSq [ i ] ; start = i ; } } // If max remaining squares = 0 then we have already // cut the entire paper if ( maxRemSq == 0 ) return 0 ; end = start ; int [] newRemSq = Arrays . copyOf ( remSq b ); int ans = Integer . MAX_VALUE ; // Find the ending point of min height while ( end < b ) { // length of edge of square from start till current end int squareEdge = end - start + 1 ; // If the current column does not have maximum remaining // squares or if it's impossible to cut a square of // size squareEdge then break out of the loop if ( newRemSq [ end ] != maxRemSq || newRemSq [ end ] - squareEdge < 0 ) break ; // If we can cut a square of size squareEdge // update the remainingSquares for ( int i = start ; i <= end ; i ++ ) newRemSq [ i ] = maxRemSq - squareEdge ; // Find the solution for new remainingSquares ans = Math . min ( ans 1 + minCutUtil ( newRemSq a b memo )); end += 1 ; } memo . put ( key ans ); return ans ; } // Function to find the minimum number of squares we can cut // using paper of size a X b static int minCut ( int a int b ) { // if the given rectangle is a square if ( a == b ) return 1 ; // Initialize remaining squares = a for all the b columns int [] remSq = new int [ b ] ; Arrays . fill ( remSq a ); Map < Integer Integer > memo = new HashMap <> (); return minCutUtil ( remSq a b memo ); } public static void main ( String [] args ) { // Sample Input int a = 13 b = 11 ; // Function call to get minimum number // of squares for axb System . out . println ( minCut ( a b )); } }
Python # Python Program to find minimum number of squares to cut # from a paper of size axb # function to get the hash key for remSq array def getKey ( remSq b ): base = 1 key = 0 for i in range ( b ): key += remSq [ i ] * base base = base * ( b + 1 ) return key # Recursive function to find the minimum number of square cuts # for a given remSq array def minCutUtil ( remSq a b memo ): # pointers to mark the start and end of range # with maximum remaining squares start = 0 # Check if we have previously calculated the answer # for the same state key = getKey ( remSq b ) if key in memo : return memo [ key ] maxRemSq = 0 # Find the starting point of min height for i in range ( b ): if remSq [ i ] > maxRemSq : maxRemSq = remSq [ i ] start = i # If max remaining squares = 0 then we have already # cut the entire paper if maxRemSq == 0 : return 0 end = start newRemSq = remSq [:] ans = float ( 'inf' ) # Find the ending point of min height while end < b : # length of edge of square from start till current end squareEdge = end - start + 1 # If the current column does not have maximum remaining # squares or if it's impossible to cut a square of # size squareEdge then break out of the loop if newRemSq [ end ] != maxRemSq or newRemSq [ end ] - squareEdge < 0 : break # If we can cut a square of size squareEdge # update the remainingSquares for i in range ( start end + 1 ): newRemSq [ i ] = maxRemSq - squareEdge # Find the solution for new remainingSquares ans = min ( ans 1 + minCutUtil ( newRemSq a b memo )) end += 1 memo [ key ] = ans return ans # Function to find the minimum number of squares we can cut # using paper of size a X b def minCut ( a b ): # if the given rectangle is a square if a == b : return 1 # Initialize remaining squares = a for all the b columns remSq = [ a ] * b memo = {} return minCutUtil ( remSq a b memo ) if __name__ == '__main__' : # Sample Input a = 13 b = 11 # Function call to get minimum number # of squares for axb print ( minCut ( a b ))
C# // C# Program to find minimum number of squares to cut // from a paper of size axb using System ; using System.Collections.Generic ; class GfG { // function to get the hash key for remSq array static int getKey ( int [] remSq int b ) { int baseVal = 1 ; int key = 0 ; for ( int i = 0 ; i < b ; i ++ ) { key += ( remSq [ i ] * baseVal ); baseVal = baseVal * ( b + 1 ); } return key ; } // Recursive function to find the minimum number of square cuts // for a given remSq array static int minCutUtil ( int [] remSq int a int b Dictionary < int int > memo ) { // pointers to mark the start and end of range // with maximum remaining squares int start = 0 end ; // Check if we have previously calculated the answer // for the same state int key = getKey ( remSq b ); if ( memo . ContainsKey ( key )) return memo [ key ]; int maxRemSq = 0 ; // Find the starting point of min height for ( int i = 0 ; i < b ; i ++ ) { if ( remSq [ i ] > maxRemSq ) { maxRemSq = remSq [ i ]; start = i ; } } // If max remaining squares = 0 then we have already // cut the entire paper if ( maxRemSq == 0 ) return 0 ; end = start ; int [] newRemSq = ( int []) remSq . Clone (); int ans = int . MaxValue ; // Find the ending point of min height while ( end < b ) { // length of edge of square from start till current end int squareEdge = end - start + 1 ; // If the current column does not have maximum remaining // squares or if it's impossible to cut a square of // size squareEdge then break out of the loop if ( newRemSq [ end ] != maxRemSq || newRemSq [ end ] - squareEdge < 0 ) break ; // If we can cut a square of size squareEdge // update the remainingSquares for ( int i = start ; i <= end ; i ++ ) newRemSq [ i ] = maxRemSq - squareEdge ; // Find the solution for new remainingSquares ans = Math . Min ( ans 1 + minCutUtil ( newRemSq a b memo )); end += 1 ; } memo [ key ] = ans ; return ans ; } // Function to find the minimum number of squares we can cut // using paper of size a X b static int minCut ( int a int b ) { // if the given rectangle is a square if ( a == b ) return 1 ; // Initialize remaining squares = a for all the b columns int [] remSq = new int [ b ]; for ( int i = 0 ; i < b ; i ++ ) remSq [ i ] = a ; Dictionary < int int > memo = new Dictionary < int int > (); return minCutUtil ( remSq a b memo ); } static void Main () { int a = 13 b = 11 ; // Function call to get minimum number // of squares for axb Console . WriteLine ( minCut ( a b )); } }
JavaScript // JavaScript Program to find minimum number of squares to cut // from a paper of size axb // function to get the hash key for remSq array function getKey ( remSq b ) { let base = 1 ; let key = 0 ; for ( let i = 0 ; i < b ; i ++ ) { key += ( remSq [ i ] * base ); base = base * ( b + 1 ); } return key ; } // Recursive function to find the minimum number of square cuts // for a given remSq array function minCutUtil ( remSq a b memo ) { // pointers to mark the start and end of range // with maximum remaining squares let start = 0 end ; // Check if we have previously calculated the answer // for the same state let key = getKey ( remSq b ); if ( key in memo ) return memo [ key ]; let maxRemSq = 0 ; // Find the starting point of min height for ( let i = 0 ; i < b ; i ++ ) { if ( remSq [ i ] > maxRemSq ) { maxRemSq = remSq [ i ]; start = i ; } } // If max remaining squares = 0 then we have already // cut the entire paper if ( maxRemSq === 0 ) return 0 ; end = start ; let newRemSq = remSq . slice (); let ans = Infinity ; // Find the ending point of min height while ( end < b ) { // length of edge of square from start till current end let squareEdge = end - start + 1 ; // If the current column does not have maximum remaining // squares or if it's impossible to cut a square of // size squareEdge then break out of the loop if ( newRemSq [ end ] !== maxRemSq || newRemSq [ end ] - squareEdge < 0 ) break ; // If we can cut a square of size squareEdge // update the remainingSquares for ( let i = start ; i <= end ; i ++ ) newRemSq [ i ] = maxRemSq - squareEdge ; // Find the solution for new remainingSquares ans = Math . min ( ans 1 + minCutUtil ( newRemSq a b memo )); end += 1 ; } memo [ key ] = ans ; return ans ; } // Function to find the minimum number of squares we can cut // using paper of size a X b function minCut ( a b ) { // if the given rectangle is a square if ( a === b ) return 1 ; // Initialize remaining squares = a for all the b columns let remSq = new Array ( b ). fill ( a ); let memo = {}; return minCutUtil ( remSq a b memo ); } // Driver Code let a = 13 b = 11 ; // Function call to get minimum number // of squares for axb console . log ( minCut ( a b ));
산출
6
시간 복잡도: O(a^b) b 열 각각에 대해 사각형을 가질 수 있습니다.
보조 공간: O(a^b) 각각의 고유한 상태를 저장하는 메모이제이션으로 인해.
