출처 : 백준
문제 보러가기 : 스티커
해당 문제는 다이나믹 프로그래밍으로 아주 간단하게 해결할 수 있는 문제이다.
우선 다이나믹 프로그래밍을 이용하기 위해서 해당 문제를 해결하기 위한 규칙을 찾고 수식을 세워야 한다.
위 그림과 같이 각각의 칸에 대한 최댓값은 한칸을 넘기는 경우( 엇박자 진행 )과 대각선으로 진행하는 경우 중 최댓값과 해당 칸에 대한 스티커의 비중의 합이다.
이 수식을 적용하여 모든 칸에 대한 각각의 최대값을 구한 다음 가장 마지막 열에 속하는 2개의 인자 중 최댓값을 뽑아내면 이 문제는 곧 바로 해결된다.
소스코드
문제 보러가기 : 스티커
해당 문제는 다이나믹 프로그래밍으로 아주 간단하게 해결할 수 있는 문제이다.
우선 다이나믹 프로그래밍을 이용하기 위해서 해당 문제를 해결하기 위한 규칙을 찾고 수식을 세워야 한다.
위 그림과 같이 각각의 칸에 대한 최댓값은 한칸을 넘기는 경우( 엇박자 진행 )과 대각선으로 진행하는 경우 중 최댓값과 해당 칸에 대한 스티커의 비중의 합이다.
이 수식을 적용하여 모든 칸에 대한 각각의 최대값을 구한 다음 가장 마지막 열에 속하는 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 |
댓글