백준 10803, 정사각형 만들기

개요

문제 링크
플래 3, Greedy, DP
N×M크기의 직사각형을 최소 개수의 정사각형으로 나누기

---

접근

1. 내 하루를 앗아간 그리디 & 메모이제이션 DP문제, 사실 접근은 분할정복에 더 가까운 것 같다. 증명 시도했는데 처참히 털렸다. 시간날 때마다 도전해보고 성공하면 수정하려고 한다.

2. 어디가 그리디인가? 싶을 수 있는데 N이 10000이니까 N^2을 돌리지 않게 하기 위해 그리디를 사용한다. 처음에는 N,M루프를 돌면서 왼쪽 위 정사각형을 하나 만들고 남은 L자 모양의 구간을 두 가지 방법으로 잘라서 최솟값을 구하는 방식으로 진행했다.

3. 그런데 이 방법은 최선이 아니다. L자 모양을 두개의 직사각형으로 자르지 않는 것이 최선이 될 수 있는데, 아래 예시를 보자.

   

4. N=72, M=35이다. 왼쪽 위 15만큼의 정사각형을 두고 L자 모양으로 자르지 않았음에도 최적의 분할인 10개가 나온다.

5. 그럼 어떻게 하냐? 하면 정해인 세로, 가로 분할을 하자. 그럼 세로는 10000번 분할인데 N^2아니냐? 아니다. 이때 그리디를 사용한다.

   1. N>=M을 만족하도록 설정해준다. 90도 회전시켜도 분할하는 방법은 같기 때문이다.
   2. 다음으로 그리디를 하기 전에 기본적인 생각을 먼저 하면, 가로와 세로가 약수나 배수의 관계면 N/M이나 M/N개를 만들어 주는게 제일 좋다.
   3. 자르는 행위는 가로 분할 혹은 세로 분할이 있으므로 모든 가로 분할, 혹은 세로 분할에 대해 재귀적으로 최솟값을 찾아준다. 이 모든 분할의 최솟값이 곧 N,M의 최소분할이 된다. 완탐을 돌린 것이기 때문에 이해는 어렵지만 맞다.
   4. 그런데 특정 조건에서는 먼저 M,M크기의 정사각형을 덜고 시작하는 것이 이득이다. 즉 세로 분할을 M번째 열에서 해주는 것이 최선이다. 가로분할이나, 다른 세로분할보다 이득인건데, 아래 내용을 더 읽어보자.

K?

1. N>=k×M에서 M번째 열의 세로분할이 최대 이득이라면, 이분탐색을 이용해 귀납적으로 k를 구해볼 수는 있다.

2. 증명은 처참히 털렸다. k의 존재성을 증명하는 것도 못했다. 성공할 때까지 틈틈이 생각해보다가 성공하면 수정해야겠다. 세로분할이 항상 이득인 케이스는 N이 M의 배수일 때인데 수식으로 보일 수가 없었다. N=M!일때 n/i + n/(m-i) > n/m을 만족해서 세로분할이 이득이었고, 나머지는 아무리 해도 풀리지 않았다.

3. 그러면 어쩔 수 없다. 이분탐색으로 k를 구해보고 규칙성이라도 찾아보자. 빨간 선이 2x, 보라색 선이 3x, 파란 범위는 $x^{1.05}, 2.3\times x$로 했다. 빨간 선을 넘어가는 점이 있기 때문에 2가 안되는 것이다.

   대표적으로 17,36이 있는데, 아래와 같이 그려주면 최선이 10개 정사각형이 된다.

   

4. 그래프의 초록 점이 100까지, 파란 점이 130까지 인데, m이 100 이상일 때는 3x, 4x로도 커버하지 못하는 값이 나온다고 하니 아마 범위는 둘 다 지수함수 일 것이다.

이 문제를 증명해줄 미래의 나를 응원하며...


[23.05.15] Bisect에서 배열 초기화를 최적화했다. 재귀 없이 3중 포문으로 업데이트 예정.

---

Bisect

#include <bits/stdc++.h>
using namespace std;

using ld=double;
using vec=vector<int>;
using mat=vector<vec>;
mat mem;
ld k;

int dp(int n,int m) {
    if (n<m) swap(n,m);
    int &r=mem[n][m];
    if (r!=2e9) return r;
    if (n%m==0) return r=n/m;
    if (n>=k*ld(m)) return r=min(r,dp(n-m,m)+1);
    for (int i=1;i*2<=n;i++)
        r=min(r,dp(n-i,m)+dp(i,m));
    for (int i=1;i*2<=m;i++)
        r=min(r,dp(n,m-i)+dp(n,i));
    return r;
}

int n,m;
ld find(ld v) {
    k=v;
    mem=mat(n+1,vec(m+1,2e9));
    return dp(n,m);
}

ld bisect() {
    ld l=0,r=4;
    ld v=find(l);
    for (int i=1;i<=10;i++) {
        ld k=(l+r)/2;
        (find(k)<v?r:l)=k;
    }
    return r;
}

int main() {
    for (m=1;m<=10;m++) {
        ld p=0;
        for (n=m*3;n<=m*4;n++) {
            ld v=bisect();
            if (v<4)
                p=max(p,v);
        }
        if (p) {
            ld v=p*ld(m);
            printf("(%d,%.3lf),",m,v);
        }
    }
}

---

Source code

#include <bits/stdc++.h>
using namespace std;

#define N 10010
#define M 110
int mem[N][M];

int dp(int n,int m) {
    if (n>=5*m/2) return dp(n-m,m)+1;
    int &r=mem[n][m];
    if (r) return r;
    r=2e9;
    if (n%m==0) return r=n/m;
    for (int i=1;i*2<=n;i++)
        r=min(r,dp(n-i,m)+dp(i,m));
    for (int i=1;i*2<=m;i++)
        r=min(r,dp(n,m-i)+dp(n,i));
    return r;
}

int main() {
    int n,m;
    cin>>n>>m;
    if (n<m) swap(n,m);
    cout<<dp(n,m);
}