백준 9465번 스티커

문제

9465

다음과 같은 2*5의 배열이 있을 때

대각선으로 1칸씩 선택했을 떄 값은 250이지만

100에서 1칸뒤가 아닌 2칸뒤인 60을 선택하면 260으로 최대값이 나온다

그러므로 1칸 뒤를 선택하는 경우 2칸뒤를 선택하는 경우중 큰 값을 더해주는 점화식을 도출한다.

dp[0][i] = st[0][i] + std::max(dp[1][i - 1], dp[1][i - 2]);
dp[1][i] = st[1][i] + std::max(dp[0][i - 1], dp[0][i - 2]);

dp배열에 최대값이 될 수 있는 값들을 저장한다.

예시

[0][2]배열에는 100이 들어있었고 2칸 뒤를 선택했을 때 [1][0] 1칸뒤를 선택했을 때[1][1]이다 둘중 더 큰 값은 1칸 뒤를 선택한 100이므로 합쳐서 200이 저장된다.

[1][4] 배열에는 60이 들어있고 2칸 뒤를 선택했을 때 [0][2] 1칸뒤를 선택했을 때 [0][3]이다 둘중 더 큰 값은 2칸 뒤를 선택한 [0][2]이므로 260이 된다.