문제링크
문제
막대 N개를 가지고 있다. 이 막대를 이용해 만들 수 있는 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.
막대는 이어 붙일 수 있고, 조각낼 수는 없다. 예를 들어, 길이가 2인 막대와 3인 막대를 합쳐 5인 막대를 만들 수 있다.
예를 들어, 가지고 있는 막대의 길이가 1, 3, 3, 4, 5, 7라면, 3 두 개와 5, 그리고 1과 4를 붙여 5를 만들면 3*5 크기의 직사각형을 만들 수 있다.
입력
첫째 줄에 막대의 개수 N이 주어진다. N은 4보다 크거나 같고, 16보다 작거나 같은 자연수이다.
둘째 줄에 막대의 길이가 공백을 사이에 두고 주어진다. 막대의 길이는 10보다 작거나 같은 자연수이다.
풀이 유형
풀이
우선 완전탐색으로 무식하게 해당 문제를 풀고자 했을 때 걸리는 시간은 O(5^n)이다. 그냥 정말 무식한 방법이다. 각 젓가락을 4개의 모서리 중 어디 둘 것인지 혹은 두지 않을 것인지 5가지의 경우를 n 거듭제곱 한 것이다. 하지만 당연히도 시간 내에 풀리지 않는다. 내 풀이 방법은 메모이제이션을 통한 분할 정복이다.
젓가락을 2그룹으로 나눈다. 그냥 무지성으로 index를 기준으로 반으로 가른다. 그 이후, 각각의 그룹에서 각자 완전탐색을 진행한다. 여기서, 메모이제이션을 통해 중복되는 케이스를 피하는 것이 내 전략이다.
내가 메모이제이션 해주는 것은 아래와 같다.
1
2
3
4
5
{ 현재까지 진행한 젓가락의 번호,
왼쪽 모서리 - 오른쪽 모서리,
윗변 - 아랫변,
왼모서리 크기,
오른 모서리 크기 }
벌써 어지럽다. 자 조금 간단히 생각해보자. 인간의 손가락 5개로 표현할 수 있는 수의 종류는 32가지다. 그것과 마찬가지로, 변수 두 개로 표현할 수 있는 방식은 4가지다. 첫 번째 변수에 더하는 경우, 첫 번째 변수에 빼는 경우, 두 번째 변수에 더하는 경우, 두 번째 변수에 빼는 경우. 나는 이것을 이용하여, 왼쪽 모서리에 올 값들은 더해주고, 오른쪽은 뺴주고, 윗변은 더해주고, 아랫변은 뺴준다는 생각으로 한 영역을 진행한다.
여기서 우리는 무수한 중복을 만난다. 윗변과 옆변은 사실 굴리면 서로 무난하게 바뀐다. 이런 경우가 완전탐색에서 빈번하게 중복되어 계산된다. 나는 map함수를 통해 그러한 경우를 체크해주기로 했다. 그래서 메모이제이션이 위의 것 처럼 되는 것이다.
1
if(dic.find({n,l,a,b,tmp1,tmp2}) != dic.end()) return ;
위의 조건문으로 중복된 경우를 계산하지 않는다.
다음으로는 직접적으로 어떻게 분할정복을 하는지의 방식을 설명하겠다.
1
2
그룹1 : dic[왼쪽 모서리 - 오른쪽 모서리][윗변 - 아랫변]
그룹2 : dic[오른쪽 모서리 - 왼쪽 모서리][아랫변 - 윗변]
그룹 1과 그룹 2에서 각각 위의 경우를 생각해보자. 두 경우가 직사각형을 이루기 위해선 어떻게 해야할까?
1
2
3
4
5
6
7
a = 왼모서리 - 오른 모서리
b = 윗변 - 아랫변
c = 오른 모서리 - 왼모서리
d = 아랫변 - 윗변
a = -b
c = -d
되려면 그룹 1에서 모은 것과 그룹 2에서 모은 것이 합쳐져서 직사각형을 이루려면 a = -b 이고 c = -d 여야 한다.
1
2
3
4
5
6
7
if(dp1.find({-a,-b}) != dp1.end()){
for(int i=0; i< dp1[{-a,-b}].size(); i++){
int t1 = dp1[{-a, -b}][i].first;
int t2 = dp1[{-a, -b}][i].second;
anw = max(anw, (tmp1+t1) * (tmp2+t2));
}
}
위에서 dp1, 즉 그룹 1에서 그룹 2의 값에 -를 취한 값들이 존재한다면, 해당 값으로 우리는 직사각형을 만들 수 있는 것이다. 그룹 1과 그룹 2 공통적으로 왼쪽 모서리와, 윗변의 길이를 저장하기 위하여 tmp1과 tmp2를 사용했다.
결론적으로, 우리는 가능한 모든 직사각형을 모두 탐색하여 그 중 최대값을 뽑아내어주면 되는 것. 만약 값이 0이라면, -1을 출력시켜주면 된다.
마무리
쉽게 말하자면, 그냥 한 변은 더하고 한 변은 빼서 0,0을 만들어주겠다는 거다. 이걸 분할시켜서 해보려고 하니, 말이 길어지고 어려워 보이는 것이다.
여담이지만, 코드는 굉장히 마음에 안 든다. 뭔가 다른 풀이가 있을 것 같은데, 억지로 시간 내에 끼워 맞춘 느낌을 지울 수 없다. 다만, 내 감상과 무관하게, 분할 정복은 꽤나 자주 이런 어려운 문제들을 푸는데 새로운 풀이법을 생가나게 해주는 것 같다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int N;
int num[17];
int anw = 0;
map<pair<int,int>, vector<pair<int,int>>> dp1;
map<tuple<int,int,int,int,int, int>, int> dic;
void dp(int n, int l, int a, int b, int tmp1, int tmp2){
if(dic.find({n,l,a,b,tmp1,tmp2}) != dic.end()) return ;
dic[{n,l,a,b,tmp1,tmp2}] = 1;
if(n==l){
if(l == (N/2)){
if(a<b) return;
if(dp1.find({a,b}) == dp1.end()){
vector<pair<int,int>> v;
dp1[{a,b}] = v;
}
dp1[{a,b}].push_back({tmp1, tmp2});
}
else{
if(a>b) return;
if(dp1.find({-a,-b}) != dp1.end()){
for(int i=0; i< dp1[{-a,-b}].size(); i++){
int t1 = dp1[{-a, -b}][i].first;
int t2 = dp1[{-a, -b}][i].second;
anw = max(anw, (tmp1+t1) * (tmp2+t2));
}
}
}
return ;
}
dp(n+1, l, a, b, tmp1, tmp2);
dp(n+1, l, a+num[n], b, tmp1+num[n], tmp2);
dp(n+1, l, a-num[n], b, tmp1, tmp2);
dp(n+1, l, a, b+num[n], tmp1, tmp2+num[n]);
dp(n+1, l, a, b-num[n], tmp1, tmp2);
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>N;
for(int i=0; i<N; i++){
int n; cin>>n;
num[i] = n;
}
dp(0, N/2, 0, 0, 0, 0);
dp(N/2, N, 0, 0, 0, 0);
anw = (anw == 0? -1 : anw);
cout<<anw<<endl;
}