Algorithm/Problem Solving 2020. 4. 16. 22:59

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

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

 

사용 알고리즘

- DP

 

풀이

- d[i][j] = 2 * i개의 스티커에서 얻을 수 있는 최대점수, i번째 열에서 뜯는 스티커는 j

- d[i][0] = max(d[i - 1][0], d[i - 1][1], d[i - 1][2]) (j = 0 : 위, 아래 모두 뜯지 않음)

- d[i][1] = max(d[i - 1][0], d[i - 1][2]) + p[i][0] (j = 1 : 위만 뜯음)

- d[i][2] = max(d[i - 1][0], d[i - 1][1]) + p[i][1] (j = 2 : 아래만 뜯음)

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/9465.cpp

#include <cstdio>

#include <algorithm>

 

using namespace std;

 

int d[100003][3];

int arr[100003][2];

 

int main(void) {

    int t; for (scanf("%d"&t); t--;) {

        int n; scanf("%d"&n);

        for (int i = 0; i < n; ++i) scanf("%d"&arr[i][0]);

        for (int i = 0; i < n; ++i) scanf("%d"&arr[i][1]);

        d[0][1= arr[0][0]; d[0][2= arr[0][1];

        for (int i = 1; i < n; ++i) {

            d[i][0= max(d[i - 1][0], max(d[i - 1][1], d[i - 1][2]));

            d[i][1= max(d[i - 1][0], d[i - 1][2]) + arr[i][0];

            d[i][2= max(d[i - 1][0], d[i - 1][1]) + arr[i][1];

        }

        printf("%d\n", max(d[n - 1][0], max(d[n - 1][1], d[n - 1][2])));

    }

    return 0;

}

Colored by Color Scripter

cs

posted by DevMoomin
: