최신 글
10
제목 게시일
10

[백준] 9465번 : 스티커

profile
코우
2021-05-13 18:27
조회 수 : 1573

출처 : 백준

문제 보러가기 : 스티커


해당 문제는 다이나믹 프로그래밍으로 아주 간단하게 해결할 수 있는 문제이다.
우선 다이나믹 프로그래밍을 이용하기 위해서 해당 문제를 해결하기 위한 규칙을 찾고 수식을 세워야 한다. 

reference

위 그림과 같이 각각의 칸에 대한 최댓값은 한칸을 넘기는 경우( 엇박자 진행 )과 대각선으로 진행하는 경우 중 최댓값과 해당 칸에 대한 스티커의 비중의 합이다. 
이 수식을 적용하여 모든 칸에 대한 각각의 최대값을 구한 다음 가장 마지막 열에 속하는 2개의 인자 중 최댓값을 뽑아내면 이 문제는 곧 바로 해결된다.
  
소스코드
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
44
45
46
#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t, n;
 
    cin >> t;
 
    while (t > 0)
    {
        cin >> n;
 
        int arr[100000][2];
        int dp[100001][2];
 
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i][0];
        }
 
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i][1];
        }
 
        dp[1][0= arr[0][0];
        dp[1][1= arr[0][1];
 
        for (int i = 2; i <= n; i++)
        {
            dp[i][0= max(dp[i - 1][1], dp[i - 2][1]) + arr[i - 1][0];
            dp[i][1= max(dp[i - 1][0], dp[i - 2][0]) + arr[i - 1][1];
        }
 
        cout << max(dp[n][0], dp[n][1]) << "\n";
 
        t--;
    }
    return 0;
}
cs
share
twitter facebook kakao naver
댓글