BOJ 2315 가로등 끄기

점화식을 세울때 시간을 하나의 요소로 넣으려고 했더니... 배열의 크기가 너무 커져서 고민하다가 그냥 백준님의 강의자료를 봤는데,

d[i][j] = i~j까지의 가로등을 껐을 때 낭비되는 전력의 최소값

처음 봤을 때는 이게 어떻게 되지? 라는 생각이 들었다. 하지만 고민해보니... 일단 i~j사이에 켜져있는 가로등이 있을 수가 없다. 즉 마지막으로 꺼지는 가로등이 중간에 있을 수 없다. 마지막으로 꺼지는 가로등은 항상 양쪽 맨 끝 중 하나일 것이다. 왜냐하면, 문제를 읽어보면 가로등을 끈 동안의 시간은 무시한다고 되어있으므로 설령 다른 전력소비량이 높은 등을 목표로 잡고 끄러 간다고 해도 지나가면서 마주치는 다른 등들은 꺼버려도 전혀 손해볼 것 없고 오히려 그렇게 해야 전력의 낭비를 최소로 할 수 있기 때문이다.

그리고 실제로 풀 때는 마지막으로 등을 끈 위치도 중요하기 때문에 0과 1로 i에 있는지, j에 있는지 위치도 표시해주어야 한다. d[i][j][where] ->  where==0이면 i를 마지막으로 끈 것이고, where==1이면 j를 마지막으로 끈 것.