색종이 올려 놓기
문제 해석
다음 두개의 조건을 만족하면서 가장 많이 쌓아올릴 수 있는 색종이 장수를 구하는 문제입니다.
- 새로 올려 놓는 색종이는 맨위의 색종이보다 크지 않아야 합니다.
- 새로 올려 놓는 색종이와 색종이의 변들은 서로 평행해야 합니다(90도 돌려 놓을 수 있습니다)
설계(10)
전형적인 dp문제입니다.
각 색종이를 시작으로 쌓을 수 있는 최대 색종이 수를 구하면 됩니다.
조건 2에서 설명한 것과 같이 색종이를 90도 돌릴 수 있기 때문에 색종이를 돌리지 않는 경우와 돌리는 경우를 각각 구해야 합니다.
구현(10)
코드
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100
pair<int,int> len[MAXN];
int cache[MAXN];
int N;
int dp(int idx){
int& ret = cache[idx];
if (ret !=-1) return ret;
ret = 1;
for (int i =0 ;i <N; i++){
if (i == idx) continue;
if (len[idx].first >= len[i].first && len[idx].second >= len[i].second){
ret = max(ret,dp(i)+1);
}
if (len[idx].first >= len[i].second && len[idx].second >= len[i].first){
ret = max(ret, dp(i)+1);
}
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
memset(cache,-1,sizeof(cache));
for (int i = 0 ;i <N; i++){
cin >> len[i].first >> len[i].second;
}
int ans = 0;
for (int i = 0 ;i <N; i++){
ans = max(ans,dp(i));
}
cout << ans <<"\n";
return 0;
}
디버깅
제출결과
0 ms