[BOJ] 1280번 나무심기

이해하기

 

- 1번부터 N번까지 X의 위치에 나무를 심는다. 이때 나무를 심는 비용은 1-N-1까지의 거리의 차이의 합이다.

- 이를 하나씩 써보면 다음과 같다. Ai = |Xi-Xi-1|+|Xi-Xi-2|+...+|Xi-X1|

- 이는 두 가지 경우로 나눌 수 있다.

- 첫번째는 현재 심으려는 위치보다 이전 경우에 심어져 있는 나무의 경우.

- 두번째는 현재 심으려는 위치보다 이후 경우에 심어져 있는 나무의 경우.

- 먼저 첫번째 경우는 현재 위치보다 이전 위치에 심어져 있는 나무의 수(pc) * 현재 심으려는 나무의 위치(x) - 이전 나무 위치들의 합(ps). 즉, pc*x-ps 로 나타낼 수 있다.

- 두번째 경우는 이후 나무 위치들의 합(ns) - 이후 위치에 심어져 있는 나무의 수(nc) * 현재 심으려는 나무의 위치(x). 즉, ns-nc*x로 나타낼 수 있다.

- 이 두가지의 경우를 합쳐서 문제에서 원하는 곱을 구하면 되는 문제이다.

- 이를 O(nlogn) 시간에 풀기 위해서는 구간 트리를 이용할 수 있다.

 

 

전체 코드

 

import java.util.Scanner;

public class B1280나무심기 {
	static final long MOD = 1000000007;
	static final int END = 200000;
	static int N;
	static long[] arr;
	static long[] tree;
	static long[] cntTree;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new long[N];
		tree = new long[END*4];
		cntTree = new long[END*4];
		
		long ans = 1;
		for(int i = 0; i < N; i++) {
			long x = sc.nextLong();
			long left = cntQuery(0,x-1,1,0,END)*x - query(0,x-1,1,0,END);
			long right = query(x+1,END,1,0,END) - cntQuery(x+1,END,1,0,END)*x;
			if(i!=0)
				ans = (left+right)%MOD * ans%MOD;
			update(x,x,1,0,END);
			cntUpdate(x,1,1,0,END);
		}
		System.out.println(ans);
		sc.close();
	}
	
	static long query(long s, long e, int node, int ns, int ne) {
		if(ne < s || ns > e) return 0;
		if(s <= ns && ne <= e) return tree[node];
		int mid = (ns+ne)/2;
		return query(s,e,node*2,ns,mid)+query(s,e,node*2+1,mid+1,ne);
	}
	
	static long cntQuery(long s, long e, int node, int ns, int ne) {
		if(ne < s || ns > e) return 0;
		if(s <= ns && ne <= e) return cntTree[node];
		int mid = (ns+ne)/2;
		return cntQuery(s,e,node*2,ns,mid)+cntQuery(s,e,node*2+1,mid+1,ne);
	}
	
	static long update(long i, long val, int node, int s, int e) {
		if(i < s || i > e) return tree[node];
		if(s==e) return tree[node]+=val;
		int mid= (s+e)/2;
		return tree[node] = update(i,val,node*2,s,mid)+update(i,val,node*2+1,mid+1,e);
	}
	
	static long cntUpdate(long i, long val, int node, int s, int e) {
		if(i < s || i > e) return cntTree[node];
		if(s==e) return cntTree[node]+=val;
		int mid= (s+e)/2;
		return cntTree[node] = cntUpdate(i,val,node*2,s,mid)+cntUpdate(i,val,node*2+1,mid+1,e);
	}
}

 

 

주의할 점

 

같은 위치에 여러개의 나무를 심으려고 하는 경우가 있다. 이를 처리해주기 위하여 단순한 구간합이 아닌 갱신을 해줄 때, 갱신할 값을 더해주는 방법으로 바꿔야 한다.

이 경우를 생각하지 못해서 한참 헤맸고 많이 틀렸다.