문제
철수에게는 빨간색, 초록색, 파란색 세 개의 버튼이 있다. 버튼 하나를 누를 때 마다 특정 점수를 얻을 수 있으며, 철수는 1초에 한 번씩 버튼을 누를 수 있다. 물론, 특정 시간에는 세 개의 버튼 중에서 한 개의 버튼만을 누를 수 있다. 각 시간마다 특정 버튼을 눌렀을 때 얻는 점수는 모두 다를 수 있다. 예를 들어, 시간 1에 빨간색, 초록색, 파란색 버튼에 대한 점수가 3, 5, 7 로 주어질 수 있다. 이 경우에는 파란색을 누르는 것이 점수를 가장 많이 얻을 수 있다. 물론, 시간 2에 각 버튼에 대한 점수는 또 다를 수 있다. 버튼을 누를 때에는 한 가지 규칙이 있는데, 연속하여 색깔이 같은 버튼을 두 번 누를 수 없다는 것이다. 예를 들어, 시간 1에 초록색 버튼을 눌렀다면, 시간 2에는 초록색 버튼을 누를 수 없다. 이와 같은 규칙으로 각 시간마다 버튼을 누른다고 할 때, 철수가 얻을 수 있는 점수의 최댓값을 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 철수에게 주어진 시간 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 두 번째 줄부터 N개의 시간에 대하여 빨간색, 초록색, 파란색 버튼을 눌렀을 때 얻을 수 있는 점수가 주어진다.
출력
철수가 얻을 수 있는 점수의 최댓값을 출력한다.
예제 입력
3
27 8 28
18 36 40
7 20 8
예제 출력
87
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <iostream>
using namespace std;
const int MAX = 300030;
int n;
int arr[MAX]={0,};
int t[MAX]={0,};
int main(){
cin>>n;
for(int i=0; i<n*3; i++){
cin>>arr[i];
}
//테이블 3개 기본 값 저장
for(int i=0; i<3; i++){
t[i] = arr[i];
}
int a, b, c, max;
for(int i=3; i<n*3; i+=3){
if(t[i-2]+arr[i] > t[i-1]+arr[i]){
a = t[i-2]+arr[i];
}else{
a = t[i-1]+arr[i];
}
t[i] = a;
if(t[i-3]+arr[i+1]>t[i-1]+arr[i+1]){
b = t[i-3]+arr[i+1];
}else{
b = t[i-1]+arr[i+1];
}
t[i+1] = b;
if(t[i-3]+arr[i+2]>t[i-2]+arr[i+2]){
c = t[i-3]+arr[i+2];
}else{
c = t[i-2]+arr[i+2];
}
t[i+2] = c;
}
a = t[n*3-3];
b = t[n*3-2];
c = t[n*3-1];
if(a>=b && a>=c){
cout<<a<<endl;
}else if(b>=a && b>=c){
cout<<b<<endl;
}else{
cout<<c<<endl;
}
return 0;
}
|
'[C++] 알고리즘 교육 > 16. 동적계획법1' 카테고리의 다른 글
[알고리즘 16.1.6] 동적계획법 - 직사각형 배치의 경우의 수 (0) | 2019.08.12 |
---|---|
[알고리즘 16.1.4] 동적계획법 - 합병정렬구현하기 (0) | 2019.08.12 |
[알고리즘 16.1.3] 동적계획법 - 구슬게임 (0) | 2019.08.12 |
[알고리즘 16.1.2] 동적계획법 - 직사각형의합 (0) | 2019.08.12 |
[알고리즘 16.1.1] 동적계획법 - 숫자만들기 (0) | 2019.08.12 |
댓글