Typescript) 백준 2104번: 부분배열 고르기

 

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

class Item<T> {
	constructor(public value: T) {}
}

type MergeFunction<T> = (this: SegmentTree<T>, nodeA: Item<T>, nodeB: Item<T>) => Item<T>;

class SegmentTree<T> {
	private lg: number;
	private sz: number;
	private n: number;
	tree: Array<Item<T>>;

	constructor(public inputArray: Array<T>, private defualtValue: Item<T>, private merge: MergeFunction<T>) {
		this.n = inputArray.length;
		this.lg = Math.ceil(Math.log2(this.n));
		this.sz = 1 << this.lg;
		this.tree = Array.from(new Array(this.sz << 1), () => defualtValue);
		this.init(inputArray, 1, 0, this.n - 1);
	}

	private pull(i: number) {
		this.tree[i] = this.merge(this.tree[i * 2], this.tree[i * 2 + 1]);
	}

	private init(array: Array<T>, node: number, start: number, end: number) {
		if (start == end) this.tree[node] = new Item(array[start]);
		else {
			this.init(array, node << 1, start, (start + end) >> 1);
			this.init(array, (node << 1) | 1, ((start + end) >> 1) + 1, end);
			this.pull(node);
		}
	}

	private _query(node: number, start: number, end: number, left: number, right: number): Item<T> {
		if (left > end || right < start) return this.defualtValue;
		if (left <= start && end <= right) return this.tree[node];
		const leftQuery = this._query(node << 1, start, (start + end) >> 1, left, right);
		const rightQuery = this._query((node << 1) | 1, ((start + end) >> 1) + 1, end, left, right);
		return this.merge(leftQuery, rightQuery);
	}

	public query(left: number, right: number) {
		return this._query(1, 0, this.n - 1, left, right);
	}
}

const input: string[] = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n');
const N = +input[0];
const arr = input[1].split(' ');

const sumFunc: MergeFunction<bigint> = (nodeA, nodeB) => {
	return new Item(nodeA.value + nodeB.value);
};

type MinInfo = { index: number; value: number };

const minFunc: MergeFunction<MinInfo> = function (nodeA, nodeB) {
	if (nodeA.value.value > nodeB.value.value) return nodeB;
	else return nodeA;
};

const minSeg = new SegmentTree<MinInfo>(
	arr.map((v, i) => ({ value: +v, index: i })),
	new Item({ index: -1, value: Infinity }),
	minFunc
);

const sumSeg = new SegmentTree(
	arr.map((v) => BigInt(v)),
	new Item(BigInt(0)),
	sumFunc
);

function query(start: number, end: number) {
	const min = minSeg.query(start, end).value;
	let max = sumSeg.query(start, end).value * BigInt(min.value);

	if (start == end) return max;

	if (start < min.index) {
		const temp = query(start, min.index - 1);
		if (max < temp) max = temp;
	}

	if (min.index < end) {
		const temp = query(min.index + 1, end);
		if (max < temp) max = temp;
	}

	return max;
}

console.log(query(0, N - 1).toString());

 

 

 

세그먼트 트리로 분리된 문제라서 풀어봤는데, 오랜만에 알고리즘 문제를 풀어서 그런건지 잘 안 풀렸다.  코드도 좀 그렇고, 

 

세그먼트트리는 사실 별로 중요하지 않고 분할정복으로 푸는 게 더 좋아보인다. 

 

세그먼트트리 클래스를 문제 풀때마다 수정하고 있는데,  범용적으로 사용할 수 있도록 작성해봐야겠다.

 

 

이 문제는... 구간 쿼리를 한다는 점에서 세그먼트 트리를 사용했는데,

 

다른 풀이를 보니 그냥 누적합 배열 만들어서 분할정복하는 게 훨씬 이해하기 쉬운 문제같다.