백준 - 가로등 끄기(2315)

문제

 

이 문제를 풀기 위해서는 가장 먼저 다음과 같은 관찰을 해야된다 :

가로등을 위치 순서대로 나타내면 가로등의 상태는 항상 켜짐, 켜짐, ... , 켜짐, 꺼짐, ... , 꺼짐, 켜짐, ... , 켜짐 형태이다.

 

그 다음으로 해볼수 있는 시도는 $\text{dp}[i][j]$를 i ~ j 번 가로등들에 대한 문제의 답으로 정의하고 점화식을 만드는 것이다. 하지만 이렇게 하면 점화식이 잘 만들어지지 않는다.

 

그 다음으로 시도해볼수 있는 것은 $\text{dp}[i][j]$를 1 ~ i, j ~ N 번 가로등을에 대한 문제의 답으로 정의하는 것이다. 실제로 이렇게 정의하면 점화식을 어렵지 않게 만들 수 있다. (다만 디테일한 부분이 구현을 어렵게 한다.)

 

끝