[C++][백준][9465] 스티커 (DP)

🍋 문제링크

www.acmicpc.net/problem/9465

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];

🍇 참조

m.blog.naver.com/occidere/220786307316

[백준] 9465 - 스티커 (2019-02-07 수정)