문제
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
풀이
N 번째 계단을 반드시 밟으면서 계단 값들의 합이 최대가 되는 경우는, N-3번째 계단과 N-1번째 계단을 밟는 경우가 있고 N-2번째 계단만 밟는 경우가 있다. 조건에 의해 3번 연속 계단을 밟을 수 없기 때문이다.
N = int(input())
stairs = [0]*10001
for i in range(1,N+1):
stairs[i] = int(input())
dp = [0]*10001
dp[1] = stairs[1]
dp[2] = stairs[1]+stairs[2]
dp[3] = max(stairs[1]+stairs[3],stairs[2]+stairs[3])
for i in range(4,10001):
dp[i] = max(dp[i-3]+stairs[i-1]+stairs[i],dp[i-2]+stairs[i])
print(dp[N])'PS > 백준' 카테고리의 다른 글
| 10844번 - 쉬운 계단 수 (1) | 2022.10.22 |
|---|---|
| 1463번 - 1로 만들기 (0) | 2022.10.22 |
| 1149번 - RGB거리 (0) | 2022.10.21 |
| 1912번 - 연속합 (0) | 2022.10.21 |
| 17822번 - 원판 돌리기 (0) | 2022.10.12 |