Interval/권영기 - Revision history

Maintenance script: Repair batch-0008 pages from live compare

2026-03-27T01:40:37Z

Repair batch-0008 pages from live compare

← Older revision		Revision as of 01:40, 27 March 2026
Line 16:		Line 16:
	using namespace std;		using namespace std;
	const int size = 120;		const int size = 120;
	int n, seq[size];		int n, seq[size];
	int d[size][size], p[size][size];		int d[size][size], p[size][size];
	queue < int > intervalQueue;		queue < int > intervalQueue;
	void findInterval(int s, int e, int* nOfInterval){		void findInterval(int s, int e, int* nOfInterval){
	if(p[s][e] == -1){		if(p[s][e] == -1){
	intervalQueue.push(e - s + 1);		intervalQueue.push(e - s + 1);
	return;		return;
	}		}
	else{		else{
	findInterval(s, p[s][e], nOfInterval);		findInterval(s, p[s][e], nOfInterval);
	findInterval(p[s][e] + 1, e, nOfInterval);		findInterval(p[s][e] + 1, e, nOfInterval);
	(*nOfInterval)++;		(*nOfInterval)++;
	}		}
Line 34:		Line 34:
	cin>>n;		cin>>n;
	for(int i = 0; i<n; i++){		for(int i = 0; i<n; i++){
	cin>>seq[i];		cin>>seq[i];
	}		}

Line 43:		Line 43:

	for(int k = x; k <= y; k++){		for(int k = x; k <= y; k++){
	if(max < seq[k])max = seq[k];		if(max < seq[k])max = seq[k];
	if(min > seq[k])min = seq[k];		if(min > seq[k])min = seq[k];
	}		}
	intervalValue = max - min;		intervalValue = max - min;
Line 50:		Line 50:
	if(x + 1 < y - 1){		if(x + 1 < y - 1){
	for(int k = x + 1; k < y - 1; k++){		for(int k = x + 1; k < y - 1; k++){
	if(intervalValue < d[x][k] + d[k+1][y]){		if(intervalValue < d[x][k] + d[k+1][y]){
	intervalValue = d[x][k] + d[k+1][y];		intervalValue = d[x][k] + d[k+1][y];
	intervalPos = k;		intervalPos = k;
	}		}
Line 57:		Line 57:
	}		}
	//find intervalValue between xth and yth by using DP table. available more than 1 interval.		//find intervalValue between xth and yth by using DP table. available more than 1 interval.
	d[x][y] = intervalValue;		d[x][y] = intervalValue;
	p[x][y] = intervalPos;		p[x][y] = intervalPos;
	}		}
	}		}
	//we only consider upper triangle of DP table. y is always greater than x.		//we only consider upper triangle of DP table. y is always greater than x.

	int intervalSum = d[0][n-1], intervalNum = 1;		int intervalSum = d[0][n-1], intervalNum = 1;
	findInterval(0, n-1, &intervalNum);		findInterval(0, n-1, &intervalNum);
	cout<<intervalSum<<endl;		cout<<intervalSum<<endl;
Line 74:		Line 74:
	return 0;		return 0;
	}		}

imported>trailblaze at 11:15, 15 July 2014

2014-07-15T11:15:57Z

← Older revision		Revision as of 11:15, 15 July 2014
Line 7:		Line 7:
	* 점화식에 대한 설명은 위에 잘 나와있다.		* 점화식에 대한 설명은 위에 잘 나와있다.
	* 문제에서는 interval의 합과 더불어 추가적으로 어떻게 구간을 나눴는지 물어본다.		* 문제에서는 interval의 합과 더불어 추가적으로 어떻게 구간을 나눴는지 물어본다.
	DP 테이블 말고 다른 2차원 테이블을 하나 추가적으로 두어(P라고 하자), 어느 위치에서 구간을 나눴는지를 표시한다. 예를 들면 P(0, 9) = 4라면, ~~우리는~~ 구간을 (0 ~ 4)와 (5 ~ 9)로 나눴다는 것. 이렇게 해서 나눠지지 않은 구간이 될 때까지 찾는다. 재귀 쓰세요.		DP 테이블 말고 다른 2차원 테이블을 하나 추가적으로 두어(P라고 하자), 어느 위치에서 구간을 나눴는지를 표시한다. 예를 들면 P(0, 9) = 4라면, 구간을 (0 ~ 4)와 (5 ~ 9)로 나눴다는 것. 이렇게 해서 나눠지지 않은 구간이 될 때까지 찾는다. 재귀 쓰세요.

	== 소스 ==		== 소스 ==

imported>trailblaze at 11:14, 15 July 2014

2014-07-15T11:14:46Z

← Older revision		Revision as of 11:14, 15 July 2014
Line 5:		Line 5:

	* [http://183.106.113.109/30stair/interval_doc/interval_doc.php?pname=interval_doc]		* [http://183.106.113.109/30stair/interval_doc/interval_doc.php?pname=interval_doc]
	* 점화식에 대한 ~~풀이는~~ 위에 잘 나와있다.		* 점화식에 대한 설명은 위에 잘 나와있다.
	* 문제에서는 interval의 합과 더불어 추가적으로 어떻게 구간을 나눴는지 물어본다.		* 문제에서는 interval의 합과 더불어 추가적으로 어떻게 구간을 나눴는지 물어본다.
	DP 테이블 말고 다른 2차원 테이블을 하나 추가적으로 두어(P라고 하자), 어느 위치에서 구간을 나눴는지를 표시한다. 예를 들면 P(0, 9) = 4라면, 우리는 구간을 (0 ~ 4)와 (5 ~ 9)로 나눴다는 것. 이렇게 해서 나눠지지 않은 구간이 될 때까지 찾는다. 재귀 쓰세요.		DP 테이블 말고 다른 2차원 테이블을 하나 추가적으로 두어(P라고 하자), 어느 위치에서 구간을 나눴는지를 표시한다. 예를 들면 P(0, 9) = 4라면, 우리는 구간을 (0 ~ 4)와 (5 ~ 9)로 나눴다는 것. 이렇게 해서 나눠지지 않은 구간이 될 때까지 찾는다. 재귀 쓰세요.

imported>trailblaze at 11:13, 15 July 2014

2014-07-15T11:13:45Z

New page

== 결과 ==
run-id user id 프로그램 명 결과 언어 경과 시간(초) 코드 사이즈(byte) 제출 시간
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;
}