백준 9465번 - 스티커

https://www.acmicpc.net/problem/9465

위쪽 행과 아래쪽 행을 구분해서 1열부터 n열까지 차례대로 값을 구해나가면 된다.

dp 점화식을 세울 때 위쪽 행을 0번째, 아래쪽 행을 1번째라고 한다면
dp[i번째열][0번째 행]=dp[i-1번째열][1번째 행]
dp[i번째열][1번째 행]=dp[i-1]번째열][0번째 행]
과 같이 0번째 행을 구할 때는 이전 열의 1번째 행을, 1번째 행을 구할 때는 반대로 하면 된다.


주의할 점은 i-2번째 열도 함께 생각해야 하는데
다행히도 문제의 예제에서 4번째 열을 모두 고려하지 않았을 때 최대값이 나오는 결과를 보여줘서 쉽게 풀 수 있던 문제이다.

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int T; cin>>T; int n; for(int testCase=0;testCase<T;testCase++){ scanf("%d",&n); int ans=0; vector<vector<int>> dp(n+1,vector<int>(2,0)); for(int i=0;i<2;i++) for(int j=1;j<=n;j++) scanf("%d",&dp[j][i]); ans=max(dp[1][0],dp[1][1]); for(int i=2;i<=n;i++){ dp[i][0]+=max(max(dp[i-2][0],dp[i-2][1]),dp[i-1][1]); dp[i][1]+=max(max(dp[i-2][0],dp[i-2][1]),dp[i-1][0]); ans=max(dp[i][0],dp[i][1]); } printf("%d\n",ans); } return 0; }