BOJ 17139 - 초라기와 쿼리

옛날에 나와 지금의 내가 어느정도 차이가 있는지 확인하고 싶어, 옛날에 접근도 못했던 1006번 초라기 문제를 자력솔 하고, 그 연계문제를 풀게 되었다.

보통 이런 넓혀나가면서 dp를 응용하는 풀이는 구간 단위로도 적용할 수 있다.
문제를 보자마자 구간 dp를 정의하고 분할 정복하면 되겠구나를 떠올렸고 이런 거는 세그먼트트리나 제곱근 분할로 해야 한다.

제곱근 분할을 사용해도 구간합을 구현해야 하기에 그냥 구현량이 적은 세그를 선택했다.

구간단위로 dp 되어있는 최적값들을 활용하여, 새로운 구간을 만들 때, 필요한 dp는 합쳐지는 경우의 수를 다 표현하는 dp를 찾으면 된다.

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

합칠 때 4중 포문을 이용하여, 간단하게 합칠 수 있다.
한 구간에 대해 16개의 dp를 만드는데 그 디피마저 각각이 디피식이 다르다.

http://boj.kr/7c0dfcebd7704fc3bff8ef38c072ddd7

공유 소스 보기

폰 코딩한 거라 독자를 위한 변수명 처리가 안되어있다. 대충 합칠 때 어떻게 포문을 돌렸는지만 보며 참고하길 바란다.
(void sum 함수에 구현이 되어있다.)

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

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

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