문제 조건을 보면 한 번 짜르면 무조건 끝까지 잘라야 하고, 수평/ 수직으로만 자를 수 있기 때문에...
d[n][m] = n * m의 직사각형을 잘라서 얻을 수 있는 정사각형 조각의 최소 개수
로 놓고, 수평으로 자르는 경우, 수직으로 자르는 경우 1 ~ n, 1 ~ m 모든 경우를 다 보면서 그 중 최소값을 얻어내면 될 것 같고,
최소값을 구해야 하므로 n == m인 경우 더 자를 필요 없이 1을 리턴해주는 식으로 구현하면 될 것 같다.
그런데, 생각해보니 그렇게 하면 시간 복잡도가 n * m * (n + m)이 될 것 같은데...
100억 정도가 되어 너무 크다. 그런데 생각해보면 n + m부분에서 n + m을 다 해볼 필요 없이, 그러니까 1 ~ n, 1 ~ m을 다 볼 필요 없이 절반까지만 보면 될 것 같다. 어차피 절반 이후로는 똑같으니까...
음... 그래도 여전히 시간복잡도가 크다. 그런데 위와 같이 절반까지만 보기 때문에 재귀로 구현하면 d[n][m]에 해당하는 n * m부분이 정말 n * m만큼 호출될 것 같지는 않다.... 일단 구현해 봐야겠다.
제출했더니 역시나 시간초과가 떴다...
어떻게 줄여야할까?
음 일단 생각나는 것이... d[w][h] 나 d[h][w]나 같다는 것이다. 이것을 한 번 적용해 봐야겠다. 그러면 또 반 정도 줄일 수 있을 거 같긴하다.
음 그런데, 저것을 적용하니 좀 답이 잘못 나온다.(10000, 100인 경우에...)
왜 그런지 이유는 잘 모르겠지만... -> 생각해보니 애초에 dp배열크기가 d[10001][101]이라 그런 것 같다. w와 h의 범위가 다르다... 그래서 배열 범위를 초과하여 잘못된 값이 들어간 것 같다.
일단 또 생각해본 것이 w나 h 둘 중 하나가 1인 경우 굳이 더 나눠 볼 필요가 없다는 것이다. 일단 이 부분을 추가해도 시간이 그리 단축되지는 않는다.
확실하지는 않은데, w와 h의 gcd(최대공약수)값부터 자르거나 최대공약수 단위로 자르는 건 어떨까? 최대공약수가 1이면 1부터 해야겠지만, 최대공약수가 2이기만 해도 엄청 많이 줄일 수 있을 것 같은데...
확실하게 증명은 할 수 없지만... 일단 최대공약수부터 시작해서 최대공약수 단위로 자르는 식으로 구현해 봐야겠다.
일단 예제에 대해서는 제대로 나오기는 하는데, 시간초과를 받았다... 9999 100 같은 케이스에 대해서는 여전히 느리다.
댓글 없음:
댓글 쓰기