목록BOJ17139 (1)

알고리즘 일지

BOJ 17139 - 초라기와 쿼리

문제 링크17139번: 습격자 초라기와 쿼리 (Normal) (acmicpc.net)습격자 초라기를 푼 사람은 알겠지만, 이런 넓혀나가면서 dp를 응용하는 풀이는 구간 단위로도 적용할 수 있다.구간단위로 적용 할 수 있으면, 바로 세그먼트 트리를 떠올릴 것이다. 구간단위로 분할 정복하는 것은 제일 쉽게 생각하면 세그먼트 트리가 유일하다. 물론 제곱근 분할법도 있지만, 어차피 구간에 대한 합을 구현해야 하니, Bucket 구현을 안 해도 되는 세그를 하는 게 마음이 편하다. 구간단위로 찾아놓은 dp 최적화 값들을 활용하여, 구간 두개를 합칠 때, 이전 찾아놓은 dp값들을 활용하면 된다. 무슨 dp값들이 필요할까?구간의 왼쪽위, 왼쪽아래, 오른쪽 위, 오른쪽아래의 사용여부에 따른 dp 값들을 관리하면 된다...
알고리즘 풀이 2024. 4. 9. 18:17
이전 Prev 1 Next 다음