[백준 15824번] 얘 봄에는 캡사이신이 맛있단다
https://www.acmicpc.net/problem/15824 처음에는 DP로 생각했으나 O(N^2) 에서 시간을 더 줄이는 것이 불가능했다. 이 문제는 모든 조합을 구하는 것은 O(2^N - 1) 로 불가능하다. 가장 중요한 추론은 어떠한 조합이든 결국 최댓값과 최솟값만 알면 스코빌지수를 알 수 있는 것이다. 1, 2, 3, 4 가 있을 때1 ,2, 41, 3, 41, 4 스코빌지수는 모두 3이다. 두번째 떠올려야할 아이디어는 위처럼 꼭 모든 조합을 해봐야알 필요는 없다. 사실 이것을 생각해내기가 가장 어려운 것 같다. 당연히 조합을 먼저 구하려고 하는 것이 일반적이기 때문이다. 1, 2, 3이 있다고 하자.3은 최댓값으로 (1, 3), (2, 3), (1, 2, 3) 으로 총 3번의 최댓값이 ..
