[BOJ 26974] Range Reconstruction

https://www.acmicpc.net/problem/26974

26974번: Range Reconstruction

 

- 문제 요약

 

Bessie에게는 a1, ... , aN의 배열이 있습니다. (1<=N<=300, 0<=ai<=10^9)
그녀는 당신에게 각각의 하위 배열의 범위를 말할 것입니다.
각 인덱스 쌍 i<=j에 대해 Bessie는 r[i, j] = max a[i...j] - min a[i...j]를 알려줍니다.
Bessie가 알려준 r값을 고려해서 배열 a를 출력하세요.
(배열의 값은 다음 범위 내에 있어야 합니다. [-10^9, 10^9])

 

 

- 알고리즘 정리

 

각 구간에서 max b[i...j] - min b[i...j]를 구해가며 나이브하게 처리해주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 301
int n,arr[MAX][MAX],result[MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n-i;j++){
			cin>>arr[i][i+j];
		}
	}
	result[1]=arr[0][1];
	for(int i=2;i<n;i++){
		if(arr[i-1][i]==0){
			result[i]=result[i-1];
			continue;
		}
		int h=result[i-1]+arr[i-1][i];
		int l=result[i-1]-arr[i-1][i];
		bool flag=false;
		for(int j=i-2;j>=0;j--){
			if(result[j]!=result[j+1]){
				int rh=max(max(result[j],result[j+1]),h)-min(min(result[j],result[j+1]),h);
				int rl=max(max(result[j],result[j+1]),l)-min(min(result[j],result[j+1]),l);
				if(rh==arr[j][i]){
					result[i]=h;
				}
				else{
					result[i]=l;
				}
				flag=true;
				break;
			}
		}
		if(!flag){
			result[i]=h;
		}
	}
	for(int i=0;i<n;i++){
		cout<<result[i];
		if(i<n-1){
			cout<<" ";
		}
	}
}

코드 제출 결과