[BOJ][DP] 9465. 스티커

문제 -> https://www.acmicpc.net/problem/9465

하나를 선택하면 상하좌우를 선택할 수가 없다.

그러면, 대각선으로만 추가적으로 계속 선택해나갈 수 있다는 말.

근데, 무조건 제일 근접한 대각선에 위치한 값만 가져와서는 안된다.

그 옆에있는 것도 고려를 해서 둘 중 큰 값을 골라야 한다.

이런식으로 구상을 할 수가 있다.

점화식은 위 그림을 토대로 

dp[0][i] = Max(dp[1][j-1], dp[1][j-2]) + dp[0][i];

dp[1][i] = Max(dp[0][j-1], dp[0][j-2]) + dp[1][i];

가 되겠다.

배열을 왜 한개만 썼냐면,

굳이 두개를 쓸 필요없이 dp배열에 초기값을 넣고서

이후 각각의 최댓값만 넣주면 더 이상 쓸 필요가 없기 때문이다.

소스(Github)