[9465번] 스티커

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 동적 프로그래밍을 위한 문제 이해

이 문제는 bottom-up(처음부터 정답을 찾아가는 과정)을 통해 해결해 보고자 한다.

table[2][100001]의 의미는 값을 입력 받는 테이블이고

ans[2][100001]의 의미는 DP를 가지는 테이블이다.

처음에 table에 값을 모두 받아주고 ans[0][0], ans[1][0], ans[0][1], ans[1][1]에 모두 초기값을 넣어준다.

4개의 ans는 자명하게 값을 구할 수 있다.

위의 그림에서 확인 할 수 있는것은 푸른색 원에 위치한 최대값을 구하기 위해서는

1번까지 더한 값을 이용하던지, 2번까지 더한 값을 이용해야 한다.

따라서 점화식은 다음과 같다.

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

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

즉, 1번 혹은 2번의 최댓값과 현재 가리키는 값을 더하여 DP로 저장하면 된다는 것이다.

마지막 출력부에서는 ans의 마지막 부분의 값 중, 0번 ans값이 큰지 1번 ans 값이 큰지 비교하면 끝이난다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <iostream> #include <algorithm>   using namespace std;   int table[2][100001]; int ans[2][100001];   int main() {     int tCase;     int n;     int max = 0;       cin >> tCase;       while (tCase--)     {         cin >> n;           for (int i = 0; i < n; i++)             cin >> table[0][i];           for (int i = 0; i < n; i++)             cin >> table[1][i];           ans[0][0] = table[0][0];         ans[1][0] = table[1][0];         ans[0][1] = table[0][1] + ans[1][0];         ans[1][1] = table[1][1] + ans[0][0];           for (int i = 2; i < n; i++)         {             ans[0][i] = table[0][i] + std::max(ans[1][i - 1], ans[1][i-2]);             ans[1][i] = table[1][i] + std::max(ans[0][i - 1], ans[0][i-2]);         }           printf("%d\n", std::max(ans[0][n - 1], ans[1][n - 1]));     } }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus