문제 2579

풀이

계단 오르는 데는 다음과 같은 규칙이 있다.
1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

1. 현재 밟고 있는 계단의 최댓값 구하기

• dp[i]: i번째까지의 합계의 최댓값
• 연속 2개 계단 가능 즉, 현재 계단을 밟으면 직전계단 또는 두개 전 계단 밟을 수 있고 직전계단을 밟으면 직전계단의 두개 전 계단을 밟아야 함.
  dp[i] = 현재 계단 + max(직전계단+dp[i-3], d[i-2])
  dp[N]을 출력하면 끝

2. 현재 밟지 않을 계단의 최솟값 구하기

• dp[i]: i번째까지의 합계의 최솟값
• 현재 계단을 밟지 않으면 직전 계단 또는 두개 전 계단을 밟아야 하므로, 두개 전 계단 또는 3개 전 계단을 밟지 않을 수 있다.
• 마지막 계단은 밟아야 하고 직전 계단 또는 두개 전 계단 중 밟지 않을 수 있음.
  dp[i] = 현재 계단 + min(dp[i-2], dp[i-3])
  전체 합계 - min(dp[i-1], dp[i-2]) 을 출력하면 끝

정답

# 1
import sys
input = sys.stdin.readline

N = int(input())
arr = [0]
for _ in range(N):
    arr.append(int(input()))
if N < 3:  # 계단개수 2개 이하
    print(sum(arr))
    exit(0)

dp = [0] * (N + 1)  # 현재 계단의 최댓값
# 1~3 초기값
dp[1] = arr[1]
dp[2] = arr[1]+arr[2]
dp[3] = max(arr[1],arr[2])+arr[3]

for i in range(4, N+1):
    dp[i] = max(arr[i-1]+dp[i-3], dp[i-2]) + arr[i]

print(dp[N])

# 2
import sys
input = sys.stdin.readline

N = int(input())
arr = [0]
for _ in range(N):
    arr.append(int(input()))
if N < 3: # 계단개수 2개 이하
    print(sum(arr))
    exit(0)

dp = [0] * (N+1) # 밟지 않을 계단 점수의 최솟값
for i in range(1,4): # index: 1,2,3 초기값 설정
    dp[i]=arr[i]

for i in range(4, N):
    dp[i] = min(dp[i-2], dp[i-3]) + arr[i]

print(sum(arr)-min(dp[N-1], dp[N-2]))

제출

위: 1번 방법
아래: 2번 방법