10803 정사각형 만들기

10803 정사각형 만들기 https://www.acmicpc.net/problem/10803
10805 L 모양의 종이 자르기 https://www.acmicpc.net/problem/10805

1. 정사각형 만들기
직사각형이 주어진다.
이 사각형으로 만들 수 있는 최대 정사각형 조각의 개수를 구하는 문제이다.

쉬운 DP구나 하고 풀었다가 TLE가 났다.
적당한 크기이상일 경우 최적화를 시켜 시간을 줄여줄 수 있다.

#include <cstdio> #include <cstring> #define INF 987654321 inline int min(int a, int b) { return a < b ? a : b; } int N, M; int dp[10001][101]; int solve(int x, int y) {     if (x == y) return dp[x][y] = 1;     if (x < 0 || y < 0) return INF;     int &ret = dp[x][y];     if (ret != -1) return ret;     ret = x*y;     //      if (x >= 4 * y) ret = min(ret, solve(x - y, y) + 1);     else {         for (int ny = 1;ny <= (y + 1) / 2;ny++)             ret = min(ret, solve(x, ny) + solve(x, y - ny));         for (int nx = 1; nx <= (x + 1) / 2;nx++)             ret = min(ret, solve(nx, y) + solve(x - nx, y));     }     return ret; } int main() {     memset(dp, -1, sizeof dp);     scanf("%d%d", &N, &M);     printf("%d\n", solve(N, M));     return 0; } Colored by Color Scripter

cs

2. L 모양의 종이 자르기 

L모양의 종이를 자를때 정사각형 조각의 최소개수를 구하는 문제이다.

가로, 세로로 잘랐을 때의 경우를 생각하면 L모양 조각이 나오는 경우와 직사각형이 나오는 경우가 있다.

이 경우들을 이용해 정사각형 조각의 개수를 구하면 된다.

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define INF 0x7fffffff int rdp[51][51]; int dp[51][51][51][51]; int rect(int a, int b) {     if (a == 0 || b == 0) return INF;     if (a == b) return 1;     if (a == 1) return b;     if (b == 1) return a;     int &ret = rdp[a][b];     if (ret != -1) return ret;     ret = INF;     for (int y = 1;y < a;y++) ret = min(ret, rect(y, b) + rect(a - y, b));     for (int x = 1;x < b;x++) ret = min(ret, rect(a, x) + rect(a, b - x));     return ret; } int solve(int a, int b, int c, int d) {     int &ret = dp[a][b][c][d];     if (ret != -1) return ret;     ret = INF;     int u = b - d, v = a - c;     for (int y = 1;y < a;y++) {         if (y < c) ret = min(ret, rect(y, u) + solve(a - y, b, c - y, d));         else if (y == c) ret = min(ret, rect(y, u) + rect(a - y, b));         else ret = min(ret, solve(y, b, c, d) + rect(a - y, b));     }     for (int x = 1;x < b;x++) {         if (x < u) ret = min(ret, rect(a, x) + solve(a, b - x, c, d));         else if (x == u) ret = min(ret, rect(a, x) + rect(v, d));         else ret = min(ret, solve(a, x, c, x - u) + rect(v, b - x));     }     return ret; } int main() {     memset(rdp, -1, sizeof rdp);     memset(dp, -1, sizeof dp);     int a, b, c, d;     scanf("%d%d%d%d", &a, &b, &c, &d);     printf("%d\n", solve(a, b, c, d));     return 0; } Colored by Color Scripter

cs