BOJ : https://www.acmicpc.net/problem/9465
GitHub : https://github.com/junho0956/Algorithm/blob/master/9465/9465/%EC%86%8C%EC%8A%A4.cpp
2*N 크기의 스티커에 점수를 두고 주어진 조건에 따라 스티커를 땟을 때 얻을 수 있는 점수가 가장 큰 경우를 구하는 것
조건 - 스티커를 때면 변을 공유하는 스티커는 때지 못한다.
생각해볼만한 부분은 이정도인 것 같다.
스티커를 다음과 같이 본다면 (n ==5)
0 1 2 3 4
5 6 7 8 9
가장먼저
dp[0][0], dp[1][0] 에 들어갈 수는 각각 0,5 가 되고
dp[0][1] 에 들어갈 수는 max(1+5, 0) dp[1][1] 에 들어갈 수는 max(6+0,5) 가 된다.
아무리 스티커를 높은점수를 위해 스티커를 원하는 것만 뽑을려고 해도 현재 스티커의 열번호(x) 기준 x-2까지만
확인하면 되니 -3 이하의 dp는 이미 동적계획법에 의해 점수를 가지고 있다고 한다면
dp[0][2] 에 들어갈 수는 dp[1][0], dp[1][1] 둘중 큰 수를 선택해서 arr[0][2] 와 더해주는 것이다.
그럼 점화식은 다음과 같다.
dp[0][x] = max(dp[1][x-1]+arr[0][x], dp[1][x-2]+arr[0][x])
더보기
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int arr[2][100000];
int dp[2][100000];
int T, n, Max;
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n;
for (int i = 0; i < 2; i++) {
for (int k = 0; k < n; k++) {
cin >> arr[i][k];
}
}
for (int i = 0; i < 2; i++) for (int k = 0; k < n; k++) dp[i][k] = 0;
dp[0][0] = arr[0][0], dp[1][0] = arr[1][0];
dp[0][1] = max(dp[0][0], dp[1][0] + arr[0][1]);
dp[1][1] = max(dp[0][0] + arr[1][1], dp[1][0]);
for (int i = 2; i < n; i++) {
dp[0][i] = max(arr[0][i] + dp[1][i - 1], arr[0][i] + dp[1][i - 2]);
dp[1][i] = max(arr[1][i] + dp[0][i - 1], arr[1][i] + dp[0][i - 2]);
}
cout << max(dp[0][n - 1], dp[1][n - 1]) << '\n';
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > BOJ' 카테고리의 다른 글
| BOJ 11053번 가장 긴 증가하는 부분수열 (0) | 2020.01.06 |
|---|---|
| BOJ 2156번 포도주 시식 (0) | 2020.01.06 |
| BOJ 11057번 오르막 수 (0) | 2020.01.06 |
| BOJ 2447번 별 찍기 - 10 (0) | 2020.01.06 |
| BOJ 10844번 쉬운 계단 수 (0) | 2020.01.06 |
