백준 20181 꿈틀꿈틀 호석 애벌레 - 효율성 혼내주기
기능성 문제를 풀고 이 문제를 처음 읽었을때 어떻게 풀지 감이 안잡혔다. 카테고리를 보니 투 포인터가 있어서 공부할때까지 미뤄두었는데, 정작 투 포인터를 공부하고도 엄청나게 헤맸다. 아래의 그림은 예제 입력에 대해 dp 테이블을 채우는 과정이다. cache[n]의 값은 먹이가 n까지 있을 때 얻을수 있는 만족도 최댓값이다. [0, 3]까지의 탈피 에너지 최댓값 + [4, 6)의 탈피 에너지 값 = 3 + 9 = 12 [0, 4]까지의 탈피 에너지 최댓값 + [5, 6)의 탈피 에너지 값 = 3 + 7 = 10 #include #include using namespace std; using ll = long long; ll psum[100001], cache[100001]; int n, k; int mai..
혼내주기
2021. 8. 1. 23:10