반응형
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
비슷한 문제: www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
방법 1. 일차원 배열로 풀기
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
long long n, ans = -1, arr[10001], dp[10001];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
dp[1] = arr[1];
dp[2] = arr[2] + arr[1];
ans = max(dp[1], dp[2]);
/*
반례
6
1000 1000 1 1 1000 1000
*/
for (int i = 3; i <= n; i++) {
// 1. i번째 잔 마심
dp[i] = arr[i] + max(arr[i - 1] + dp[i - 3], dp[i - 2]);
// 2. i번쨰 잔 안 마심
dp[i] = max(dp[i - 1], dp[i]);
ans = max(ans, dp[i]);
}
cout << ans;
}
|
cs |
방법 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
|
#include <iostream>
#include <algorithm>
using namespace std;
int n, arr[10001], dp[3][10001];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
dp[0][1] = 0; // 0번 연속 마심 (i번째 X)
dp[1][1] = arr[1]; // 1번 연속 마심 (i번째 O, i-1번째 X)
dp[2][1] = arr[1]; // 2번 연속 마심 (i번째 O, i-1번째 O)
dp[0][2] = arr[1];
dp[1][2] = arr[2];
dp[2][2] = arr[1] + arr[2];
for (int i = 3; i <= n; i++) {
dp[0][i] = max(dp[0][i - 1], max(dp[1][i - 1], dp[2][i - 1]));
dp[1][i] = arr[i] + dp[0][i - 1];
dp[2][i] = arr[i] + dp[1][i - 1];
}
cout << max(dp[0][n], max(dp[1][n], dp[2][n])) << endl;
}
|
cs |
반응형