시나브로

이 문제는 전형적인 DP 문제입니다. 하지만, DP에 약한 저는 타블로그를 참고하여 포인트를 얻었습니다. ㅠㅜ Solution 문제를 읽어보면, 2가지의 규칙을 찾을 수 있습니다. 침공당한 도시의 인접한 도시는 침공할 수 없다. -> 침략을 하면 무조건 한칸은 뛰어야한다. 도시는 침공 당한 도시와 당하지 않는 도시로 나뉘어진다. 이 두가지 규칙을 가지고 DB식을 세울 수 있습니다. DB[i] = max(DB[i-1],DB[i-2]+problem[i]); DB[i]는 i-1번째 도시까지의 max값(DB[i-1])이랑 i-2번째 도시를 방문하고 i번째의 도시를 방문하는 값(DB[i-1]+problem[i])을 비교하여 더 큰값을 가지면 됩니다. Key Point 왜인지 모르겠지만, 타임오버가 났다. 이를 해..