결과 ¶
run-id user id 프로그램 명 결과 언어 경과 시간(초) 코드 사이즈(byte) 제출 시간
1371369 zeropage interval accept C++ 0.05 1404 2014-07-15 19:59
1371369 zeropage interval accept C++ 0.05 1404 2014-07-15 19:59
풀이 ¶
- http://183.106.113.109/30stair/interval_doc/interval_doc.php?pname=interval_doc
- 점화식에 대한 설명은 위에 잘 나와있다.
- 문제에서는 interval의 합과 더불어 추가적으로 어떻게 구간을 나눴는지 물어본다.
DP 테이블 말고 다른 2차원 테이블을 하나 추가적으로 두어(P라고 하자), 어느 위치에서 구간을 나눴는지를 표시한다. 예를 들면 P(0, 9) = 4라면, 우리는 구간을 (0 ~ 4)와 (5 ~ 9)로 나눴다는 것. 이렇게 해서 나눠지지 않은 구간이 될 때까지 찾는다. 재귀 쓰세요.
소스 ¶
#include<iostream>
#include<queue>
using namespace std;
const int size = 120;
int n, seq[size];
int d[size][size], p[size][size];
queue < int > intervalQueue;
void findInterval(int s, int e, int* nOfInterval){
if(p[s][e] == -1){
intervalQueue.push(e - s + 1);
return;
}
else{
findInterval(s, p[s][e], nOfInterval);
findInterval(p[s][e] + 1, e, nOfInterval);
(*nOfInterval)++;
}
}
int main(void){
cin>>n;
for(int i = 0; i<n; i++){
cin>>seq[i];
}
for(int interval = 1; interval <= n-1; interval++){
for(int x = 0; x < n - interval; x++){
int y = x + interval, max = 0, min = 999999, intervalValue, intervalPos = -1;
for(int k = x; k <= y; k++){
if(max < seq[k])max = seq[k];
if(min > seq[k])min = seq[k];
}
intervalValue = max - min;
//find intervalValue between xth and yth. only 1 interval.
if(x + 1 < y - 1){
for(int k = x + 1; k < y - 1; k++){
if(intervalValue < d[x][k] + d[k+1][y]){
intervalValue = d[x][k] + d[k+1][y];
intervalPos = k;
}
}
}
//find intervalValue between xth and yth by using DP table. available more than 1 interval.
d[x][y] = intervalValue;
p[x][y] = intervalPos;
}
}
//we only consider upper triangle of DP table. y is always greater than x.
int intervalSum = d[0][n-1], intervalNum = 1;
findInterval(0, n-1, &intervalNum);
cout<<intervalSum<<endl;
cout<<intervalNum<<endl;
while(!intervalQueue.empty()){
cout<<intervalQueue.front()<<" ";
intervalQueue.pop();
}
return 0;
}
