🍋 문제링크

9465번: 스티커

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 2676 KB

시간 : 132 ms

🍉 Code

#include <stdio.h>
#include <algorithm>

int dp[2][100001], arr[2][100001];
int main(){
    int t, n, i, j;   
    scanf("%d", &t);

    while(t--)
    {
        scanf("%d", &n);
		for (i = 0; i <= 1; i++)
			for (j = 1; j <= n; j++) 
				scanf("%d", &arr[i][j]);

		dp[0][0] = dp[1][0] = 0;
		dp[0][1] = arr[0][1];	
    dp[1][1] = arr[1][1];

		for (i = 2; i <= n; i++) {
			dp[0][i] = std::max(dp[1][i - 1], dp[1][i - 2]) + arr[0][i];
			dp[1][i] = std::max(dp[0][i - 1], dp[0][i - 2]) + arr[1][i];
		}
		printf("%d\\n", std::max(dp[0][n], dp[1][n]));
    }
    return (0);
}

🥝 메모

📌 현재 스티커에서 선택을 할 수 있는 스티커는 1칸 오른쪽 대각선 or 2칸 오른쪽 대각선을 선택할 수 있다

그 중에서 최댓값이 되는 값을 선택하는 것이 good

각 위치에서의 최댓값을 가지는 dp 배열을 추가로 생성

<공식>

0번째 줄

$dp[0][i] = arr[0][i] + Max(dp[1][i-1], dp[1][i-2])$

1번째 줄

$dp[1][i] = arr[1][i] + Max(dp[0][i-1], dp[0][i-2])$

📌 2번째 ~ n번째 까지 순서대로 위의 공식을 대입

<초기화>

dp[0][0] = 0;
dp[1][0] = 0;
dp[0][1] = arr[0][1];	
dp[1][1] = arr[1][1];

🍇 참조