<aside> 💡

완전 탐색 For > 재귀함수 (백트래킹)

최적화 정수론 > 재귀함수 / 백트래킹의 경우의 수

기억 누적합 > 탑다운 dp, 바텁업 dp 메모이제이션

</aside>

누적합 → 컴퓨터에게 기억하는 방법을 알려주기 !

prefix 를 만들어주자 !

prefix 값을 가지고 간격 더하기 값을 구할 수 있다.

how ?

prefix 에서 두 칸 전의 값과 빼면 간격 더하기 값이 나온다.

ex) -12 - 1 = -13

이렇게 누적합 값을 한 번 계산해 놓으면, 그 값을 가지고 계산 정답을 구할 수 있다.