백준 : 2579번, 계단 오르기

문제 주소 : www.acmicpc.net/problem/2579

정답 비율 : 35.262% (2021.05.04 17:31 기준)

2579번: 계단 오르기

문제 요약 :

평지에서 N개의 계단을 오를 예정입니다. 이때 다음과 같은 조건이 걸립니다.

1. 한 번에 한 칸 또는 두 칸의 계단을 오를 수 있습니다.

2. 연속된 세 칸의 계단은 밟을 수 없습니다.

3. 마지막 계단은 반드시 밟아야합니다.

 

문제 조건 :

입력 : 계단의 개수 N이 주어집니다. 이어서 N개의 계단의 점수가 주어집니다. ( N : 1 ~ 300, 점수 : 1 ~ 10000 )

출력 : 계단 올라갔을 때 얻을 수 있는 최대 점수를 출력하시오.

시간 : 1초

 

문제 풀이 :

문제를 읽으면 가장 먼저 떠오르는 것은 DP를 사용하는 것입니다.

(간단하다고 생각했지만 점화식 구하기 힘들었습니다.)

 

DP[i]는 i번째 계단을 마지막 계단이라고 가정했을 때 얻을 수 있는 최대 점수를 의미합니다. i번째 계단을 밝을 수 있는 방법은 i - 1 또는 i - 2에서 밟을 수 있습니다. 이때 i - 2에서 i번째 계단을 밟을 때 연속 세 칸에 대해서 별도로 고민하지 않아도 됩니다. 하지만 i - 1에서 i번째 계단을 밟을 때 연속 세 칸을 신경 써야 합니다.

 

이를 바탕으로 다음과 같은 점화식을 세울 수 있습니다.

 

i < 3

DP[0] = stair[0];

DP[1] = stair[0] + stair[1];

DP[2] = stair[0] + stair[2] 와 stair[1] + stair[2] 중 더 큰 값에 해당합니다.

 

i >= 3

DP[i] = stair[i] + stair[i - 1] + DP[i - 3] 또는 stair[i] + DP[i - 2] 중 더 큰 값이 되겠습니다.

 

코드는 다음과 같습니다.

 

Python3

# solve 1920
size = int(input())
stair = [int(input()) for i in range(size)] + [0, 0]
DP = [0 for i in range(size + 2)]

DP[0] = stair[0]
DP[1] = stair[0] + stair[1]
DP[2] = max(stair[0], stair[1]) + stair[2]

for i in range(3, size):
    DP[i] = max(DP[i - 2], stair[i - 1] + DP[i - 3]) + stair[i]

print(DP[size - 1])

-> stair과 DP에 각각 size + 2 만큼 만든 이유는 아래 DP[2] 형식으로 무조건적으로 접근하기 때문입니다. size 1 또는 2가 주어진 경우에는 컴파일 에러가 발생하는 것을 방지 위함입니다.