크기가 n × m인 직사각형이 있다고 가정해 보겠습니다. 이때 변의 길이가 정수인 정사각형 조각들을 사용해 직사각형을 빈틈없이 채울 때 필요한 정사각형의 최소 개수를 구하는 것이 문제입니다.
예를 들어 입력이 n = 2, m = 3이라면 다음과 같습니다.
세 개의 정사각형 블록으로 직사각형을 완전히 덮을 수 있으므로 출력값은 3이 됩니다.
해결 접근 방식
이 문제는 DFS(깊이 우선 탐색)와 메모이제이션을 결합하여 해결할 수 있습니다. 핵심 아이디어는 각 열의 현재 채워진 높이를 추적하고, 항상 가장 낮은 위치부터 정사각형을 배치하면서 가능한 모든 경우를 탐색하는 것입니다.
DFS 함수(dfs)의 동작 단계
방문한 상태를 기록할 맵(map) s를 하나 정의합니다.
res := 무한대(inf)로 초기화합니다.
n, m, 높이 배열 h, 현재 사용 개수 cnt를 매개변수로 받는 dfs() 함수를 정의합니다.
cnt >= res이면 즉시 반환합니다. 이미 찾은 답보다 나아질 수 없기 때문입니다(가지치기).
isFull := true로 설정합니다.
pos := -1, minH := inf로 초기화합니다.
i를 1부터 n까지 반복합니다.
h[i] < m이면 isFull := false로 갱신합니다(아직 비어 있는 공간이 존재).
h[i] < minH이면 minH := h[i], pos := i로 갱신합니다(가장 낮은 열의 위치와 높이를 기록).
isFull이 참이면(모든 열이 꽉 찼으면) res := min(res, cnt)로 갱신한 뒤 반환합니다.
key := 0, base := m + 1로 설정합니다.
i를 1부터 n까지 반복하며 key에 h[i] × base를 누적하고 base를 (m + 1)배씩 곱합니다. 즉, 현재 높이 상태를 하나의 고유한 정수 키로 인코딩합니다.
key가 s에 이미 존재하고 s[key] <= cnt라면 반환합니다. 같은 상태를 더 적은 블록 수로 방문한 적이 있다는 의미이므로 더 탐색할 필요가 없습니다.
s[key] := cnt를 저장합니다.
end := pos로 설정합니다.
(end + 1 <= n 이고 h[end + 1] == h[pos] 이고 (end + 1 − pos + 1 + minH) <= m)인 동안 end를 1씩 증가시켜, 해당 위치에 놓을 수 있는 정사각형의 최대 폭을 계산합니다.
j를 end부터 pos까지 감소시키며 반복합니다.
curH := j − pos + 1 (이번에 놓을 정사각형의 한 변 길이)
크기 n + 1짜리 배열 next를 만들고 h의 값을 복사합니다.
k를 pos부터 j까지 반복하며 next[k] += curH를 적용해 정사각형을 배치한 결과를 만듭니다.
dfs(n, m, next, cnt + 1)을 재귀 호출합니다.
메인(main) 로직
n == m이면 정사각형 하나로 채울 수 있으므로 1을 반환합니다.
n > m이면 swap(n, m)으로 두 값을 교환해 항상 n ≤ m이 되도록 합니다.
크기 n + 1짜리 높이 배열 h를 생성합니다(초기값은 모두 0).
dfs(n, m, h, 0)을 호출합니다.
res를 반환합니다.
다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map<int, int> s;
int res = INT_MAX;
void dfs(int n, int m, vector<int> h, int cnt){
if (cnt >= res)
return;
bool isFull = true;
int pos = -1, minH = INT_MAX;
for (int i = 1; i <= n; i++) {
if (h[i] < m)
isFull = false;
if (h[i] < minH) {
minH = h[i];
pos = i;
}
}
if (isFull) {
res = min(res, cnt);
return;
}
long key = 0;
long base = m + 1;
for (int i = 1; i <= n; i++) {
key += h[i] * base;
base *= m + 1;
}
if (s.find(key) != s.end() && s[key] <= cnt)
return;
s[key] = cnt;
int end = pos;
while (end + 1 <= n && h[end + 1] == h[pos] && (end + 1 - pos + 1 + minH) <= m)
end++;
for (int j = end; j >= pos; j--) {
int curH = j - pos + 1;
vector<int> next(n + 1);
for (int i = 1; i <= n; i++)
next[i] = h[i];
for (int k = pos; k <= j; k++) {
next[k] += curH;
}
dfs(n, m, next, cnt + 1);
}
}
int tilingRectangle(int n, int m){
if (n == m)
return 1;
if (n > m)
swap(n, m);
vector<int> h(n + 1);
dfs(n, m, h, 0);
return res;
}
};
main(){
Solution ob;
cout << (ob.tilingRectangle(2, 3));
}입력
2,3
출력
3