알고리즘/Backjoon
[C] 2579 - 계단 오르기
ShinDongJun
2020. 1. 11. 10:44
문제 링크 : https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩
www.acmicpc.net
|
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
|
#include <stdio.h>
#include <string.h>
#define max(a,b) (a > b ? a : b)
#pragma warning(disable:4996)
int dp[10005];
int stair[10005];
int main(){
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &stair[i]);
dp[1] = stair[1];
dp[2] = stair[1] + stair[2];
dp[3] = max(stair[1] + stair[3], stair[2] + stair[3]);
if (n <= 3) {
printf("%d",dp[n]);
return 0;
}
for (int i = 4; i <= n; ++i)
dp[i] = max(dp[i - 3] + stair[i - 1] + stair[i], dp[i - 2] + stair[i]);
printf("%d", dp[n]);
}
|