https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
문제 해결을 위한 과정
이 문제를 해결하는데 있어서 가장 중요한 것은 마지막 계단을 밟아야 한다는 것이며 첫번째 계단을 밟지 않아도 된다는 것 입니다. 문제의 규칙에 따르면 다음과 같습니다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
먼저 계단이 한개일때 최대 점수는 다음과 같습니다.
첫 번째 계단이자 마지막 계단을 밟는 경우 -> 10점
계단이 두개일때 최대 점수는 다음과 같습니다.
첫 번째 계단과 마지막 계단을 밟는 경우 ->10 + 20점
계단이 세개일때 최대 점수는 다음과 같습니다.
두번째 계단과 마지막 계단을 밟는 경우 -> 20 + 15점
계단이 네개일때 최대 점수는 다음과 같습니다.
첫번째 계단과 두번째 계단 및 네번째 계단을 밟는 경우 -> 10 + 20 + 25점
다만 세번째 부터 다음과 같은 규칙이 적용되는것을 알 수 있습니다. (단, 마지막 계단이 n번째 일때)
최대의 점수 = max(n번째 계단 + n-2번째 까지의 최대 점수, n번째 계단 + n-1번째 계단 n-3번째 까지의 최대 점수)
이를 소스코드로 표현하면 다음과 같습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
n = int(input())
data = [0] * 301
for i in range(n):
data[i] = int(input())
dp = [0] * 301
dp[0] = data[0]
dp[1] = data[0] + data[1]
dp[2] = max(data[2] + data[1], data[2] + data[0])
for i in range(3, n+1):
dp[i] = max(data[i] + data[i-1] + dp[i-3], data[i] + dp[i-2])
print(dp[n-1])
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1149번: RGB거리(Python) (0) | 2022.01.24 |
|---|---|
| 백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python) (0) | 2022.01.20 |
| 백준 알고리즘 1003번: 피보나치 함수(Python) (0) | 2022.01.19 |
| 백준 알고리즘 7569번: 토마토(Python) (0) | 2022.01.15 |
| 백준 알고리즘 10026번: 적록색약(Python) (0) | 2022.01.15 |