2. 문제 요약: 각 계단마다 점수가 주어져 있고, 다음 규칙에 따라 계단을 오를 경우, 점수의 최대값을 구하는 문제이다.
<조건>
계단을 오를 때, 다음 계단으로 가거나, 다음 다음 계단으로 오를 수 있다.
3개의 연속된 계단에서 모두 점수를 얻을 수는 없다
3. 문제 접근법
문제를 다음과 같이 분할하자.
1번째 계단이 목표일 때 얻을 수 있는 최대값
2번째 계단이 목표일 때 얻을 수 있는 최대값
...
N번째 계단이 목표일 때 없을 수 있는 최대값
차근차근 계산을 하되, 주어진 마지막 n번째 계단은 반드시 밟아야 하므로 그 계단을 기준으로 가능한 경우의 수는 다음과 같다.
첫째, 마지막 계단을 밟되, 이전에 밟은 계단은 마지막 계단의 이전 이전 계단인 경우
둘째, 마지막 계단을 밟되, 이전에 밟은 계단은 마지막 계단의 이전 계단이고, 그 전에 밟은 계단은 마지막 기준으로 이전 이전 이전 계단인 경우
max를 이용하여 각 문제를 차근차근 풀고, 최종적으로 원하는 값은 N번째로 구한 값이 된다.
C 코드
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
|
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
int N;
scanf("%d", &N);
int *S = (int*)malloc(sizeof(int) * (N + 1));
int *dp = (int*)malloc(sizeof(int) * (N + 1));
S[0] = 0;
for(int i = 1; i <= N; i++)
{
scanf("%d", &S[i]);
dp[i] = 0;
}
dp[1] = S[1];
for(int i = 2; i <= N; i++)
{
dp[i] += S[i] + max(dp[i - 2], dp[i - 3] + S[i - 1]);
}
printf("%d\n", dp[N]);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기