[백준/BOJ] 백준 20181번 : 꿈틀꿈틀 호석 애벌레 - 효율성

https://www.acmicpc.net/problem/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net vector cache(100001, 0)을 사용하여 [위치] = 해당 위치에서 끝날 때 최댓값을 업데이트시키는 방법을 이용하였고, 이 과정에서 투 포인터를 이용해서 문제를 해결했다. cache를 업데이트시키는 방법은 cache[right] = max(cache[right], cache[right - 1])를 하고 난 뒤, right를 포함시키면 k이상이 되는 경우 cache..

2021.11.22