[백준 10803번] 정사각형 만들기 (Python3)

def DFS(n,m):
  if n==m:
    DP[n][m] = 1
    return
  DP[n][m] = n*m
  for n1 in range(1,n//2+1):
    n2 = n-n1
    n1,m1,n2,m2 = max(n1,m),min(n1,m),max(n2,m),min(n2,m)
    if not DP[n1][m1]:
      DFS(n1,m1)
    if not DP[n2][m2]:
      DFS(n2,m2)
    DP[n][m] = min(DP[n][m],DP[n1][m1]+DP[n2][m2])
  for m1 in range(1,m//2+1):
    m2 = m-m1
    n1,m1,n2,m2 = max(n,m1),min(n,m1),max(n,m2),min(n,m2)
    if not DP[n1][m1]:
      DFS(n1,m1)
    if not DP[n2][m2]:
      DFS(n2,m2)
    DP[n][m] = min(DP[n][m],DP[n1][m1]+DP[n2][m2])

N,M = map(int,input().split()); N,M = max(N,M),min(N,M)

c = 0
if N>M*3:
  c = (N-M*2)//M; N -= M*c

DP = [[0]*(M+1) for i in range(N+1)]
DFS(N,M)
print(DP[N][M]+c)

DP를 이용해서 해결하였다.

 

문제풀이의 핵심은 N과 M의 범위에 있다. N의 범위는 10000까지로 매우 크지만, M의 범위는 100으로 제한되어있기 때문이다. 따라서 N이 M에 비해서 매우 클 경우, 적당량을 길이가 M인 정사각형으로 잘라내고 나머지 부분만을 가지고 하면 시간복잡도를 크게 줄일 수 있다.

 

따라서 나는 N이 M*3보다 큰 경우 M*M 정사각형으로 잘라내어주었다. 즉, N-2M을 M으로 나눈 몫만큼 결과에 더해주고, 몫*M만큼을 N에서 빼준다.

 

이후 DP 풀이를 설명하면,

1. n=m이면 DP[n][m]=1

2. 1에 해당하지 않는 경우 n을 1~n//2의 길이로 잘랐을 때의 값과 m을 1~m//2의 길이로 잘랐을 때의 값의 최솟값을 구한다.

3. DP[N][M]을 출력한다.

 

 

풀이는 간단하지만 이것이 항상 최적해를 보장하는지에 대한 증명은 하지 못하였다. 원래 N이 M*2보다 큰 경우 잘라내주는 방식으로 풀었는데 틀렸습니가 떠서 3으로 늘렸더니 맞았다. (36,17이라는 반례가 존재한다)

엄밀한 증명이 까다로운 문제였다.

 

 

오늘의 교훈) 왜 3*M보다 크면 성립하는지 고민해보자