사담
#2133 타일 채우기 O(N) DP
이어붙일 수 있는 형태가 규칙적입니다.
DP[i]=DP[i-1]+2*(DP[i-2]+DP[i-4]+DP[i-6]~~~)
#2001 보석 줍기 O(N) Floyd-Warshall, bitDP
사실 DP+백트래킹으로도 풀 수 있습니다. 삽질했지만 플로이드 와샬의 메인 아이디어의 이해도를 높이기 위한 경험치가 되었습니다 ㅋㅋ
플로이드 와샬을 쓰는 건 아니고 k, i, j 순으로 원하는 거 넣고 돌리는 거 유사하게 i번째 섬에서 j번째 섬으로 갈 때 챙길 수 있는 보석의 최대 무게를 구합니다.
그리고 bitDP 돌리면서 답 구하면 되는데
놓치기 쉬운 부분은 1번섬에 보석이 있으면 돌아와서 보석 하나 더 챙길 수 있다는 거
코드보기
#7469 k번째 수 O(NlgN+MlgN) Persistent Segment Tree, Parametric Search
머지소트 트리 + 파라메트릭 서치로도 풀 수 있습니다. 이분탐색 싫어서 PST 복습할 겸 PST로 짯는데 어차피 해야했습니다 ㅋㅋ;
좌표압축하고, 좌표 순으로 인덱스를 추가하며 ( 1 증가 ) PST를 구성해주며 됩니다. (다른 방법도 많을 것 같아요)
쿼리 처리는 이분탐색으로 하는데, 1부터 n사이를 Parametric Search로 처리한다. query(mid, l, r)을 가지고 판별하는데, 이때 가능한 mid 중 가장 작은 게 답이 된다는 점에 주의해서 짜면 됩니다. 최솟값이 아닌 mid는 똑같이 query에서 k를 반환해도, l과 r범위 바깥에 있습니다.
#16978 수열과 쿼리3 O(NlgN+MlgN) Persistent Segment Tree
PST 기본 구현 문제입니다. 7469에서 PST 구현 삽질했어서 연습겸 한 번 더 짜봤습니다 ㅎ...