BOJ 17139 - 초라기와 쿼리

문제 링크

• 17139번: 습격자 초라기와 쿼리 (Normal) (acmicpc.net)

습격자 초라기를 푼 사람은 알겠지만, 이런 넓혀나가면서 dp를 응용하는 풀이는 구간 단위로도 적용할 수 있다.

구간단위로 적용 할 수 있으면, 바로 세그먼트 트리를 떠올릴 것이다. 구간단위로 분할 정복하는 것은 제일 쉽게 생각하면 세그먼트 트리가 유일하다.

 

물론 제곱근 분할법도 있지만, 어차피 구간에 대한 합을 구현해야 하니, Bucket 구현을 안 해도 되는 세그를 하는 게 마음이 편하다.

 

구간단위로 찾아놓은 dp 최적화 값들을 활용하여, 구간 두개를 합칠 때, 이전 찾아놓은 dp값들을 활용하면 된다.

 

무슨 dp값들이 필요할까?

구간의 왼쪽위, 왼쪽아래, 오른쪽 위, 오른쪽아래의 사용여부에 따른 dp 값들을 관리하면 된다.

쉽게 하는 방법은, 비트마스킹을 이용하는 것이다. 비트마다, 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래를 쓰는 경우를 표현하여 dp최적값을 적용한다.

구간을 합칠 때는, 구간의 왼쪽원소만 쓰는 배열과, 오른쪽만 쓰는 배열을 만들어 놓고, 합칠 때 4중 포문을 이용하는 게 깔끔했다.

한 구간에 대해 16개의 dp를 만드는데 그 디피마저 각각이 디피식이 다르다. 괜히 많은 조건 분기가 달린게 아니다.

 

다음 코드는 왼쪽구간 a와 오른쪽 구간 b를 합치는 sum 함수의 구현이다.

int rights[4] = {1<<1, 1<<3, p(1,3), 0};
int lefts[4] = {1<<0, 1<<2, p(0,2), 0};

void sum(node &ans, node &a, node &b) {
	if(a.dp[0] == -1) {
		ans.cop(b);
		return;
	}
	if(b.dp[0] == -1) {
		ans.cop(a);
		return;
	}
    
	int L = a.R, R = b.L;
	for(int r : rights) for(int l : lefts) {
    		//target 은 이번에 찾아낼, 합쳐진 구간의 사용하는 원소들
		int target = r|l;
        	int la=0;
		
		for(int rr : rights) for(int ll : lefts) {
			if(rr==0 || ll==0) continue;
            
            	//lt 와 rt는 구간을 합칠때, 가운데에서 이미 사용 되어지고 있는 원소들이다.
			int lt = l|rr;
			int rt = r | ll;
			
			t[la++] = a.dp[lt]+b.dp[rt];
		}
		
		t[0] += check({1, L}, {1,R});
		t[1] += 2;
		t[2] += 1;
		t[3] += 2;
		t[4] += check({0, L}, {0, R});
		t[5] += 1;
		t[6] += 1;
		t[7] += 1;
		
		int &x = ans.dp[target];
		x = a.dp[l] + b.dp[r] + check({0,L}, {0,R})+check({1,L}, {1,R});
		for(int u : t) x=min(x, u);
	}
	
	ans.L = a.L;
	ans.R = b.R;
}

구조체 세그를 악랄하게 요구하는 문제이다.

분기가 꽤 있는 까다로운 구조체 세그 문제였으니 경지상승을 위한다면 풀어보아야 할 필수 문제라고 생각된다.

세그먼트 트리의 구간활용에 끝판왕인 연결요소와 쿼리는 도대체가 어떻게 푸는 걸까?