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;
}
| cs |
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;
}
| cs |
