동적계획법 야매 테크닉(?)

안녕하세요.. 휴가나온 구닌 아조씨입니다.

음 휴가 때 게임(리그오브.. ) 를 하다 로딩 창때 심심해서 블로그도 만들고 글도 써보네요 ㅎㅎ

과연 보실 분이 있을 까 모르겠지만 한번 적어봅니다.

제가 문제를 풀다가 좋은 동적 계획법 풀이가 있어서 가져와봅니다.

이 풀이는 간단합니다.

문제로 설명드리자면 백준온라인 저지 2912 백설공주와 난쟁이란 문제가 있습니다.

링크 -> https://www.acmicpc.net/problem/2912

이 문제를 저는 이 풀이대로 풀었습니다.

처음에 일단 색깔 갯수가 1000개 이상인 것들을 미리 구해놓고 위치까지도 기록해둡니다.

그리고 쿼리가 들어올 때

R-L 이 1000보다 작으면 그냥 반복문 돌려서 구합니다.

하지만 R-L 이 1000 보다 크다면 미리 구해논 색깔 갯수가 1000개 이상인 것들 중에서 lower_bound 해서 찾아주시면 됩니다.

이렇게 되면 시간복잡도가 M*(max(1000,(N/1000)*log(N)))입니다.

왜냐하면 N이 300000이면 1000개 이상의 색깔이 300개 뿐이고 그 중에서만 생각하기 때문에 300*log(N) 이 됩니다.

그리고 팁을 들이자면 쿼리 갯수에 따라 1000 이란 기준치를 줄이거나 늘릴 수 있다는 것입니다.

백설공주와 난쟁이 문제에선 쿼리의 갯수가 10000개라 기준치를 1000으로 뒀지만

만약 100000 개라고 가정했을 땐 1000개로 잡으면 위험할 수 있으니 300~500으로 잡아주시면 되겠습니다.

즉 전체 집합에서 일정 숫자보다 큰 집합과 작은 집합을 나누어서 따로 계산해주면 시간을 야매(?) 로 줄일 수 있습니다!!