[백준] 2579번 : 계단 오르기

 

 

접근법

- 문제를 처음에 잘못 이해를 해서 첫 번째 계단을 무조건 밟아야 된다고 생각을 했다. 하지만 2칸 점프가 가능하니 N=3인 경우 2, 3번 계단만 밟아도 된다는 것을 인지했다.

 

- 입력받은 값들을 val이라는 리스트에 넣어주고, 계단이 1층인 경우(N = 1) val[0]의 값을 stare에 넣어준다. stare은 2중 배열로 두 번째 값은(stare[1][1]) 현재 연속된 계단이 몇 개인지를 기록하는 지표이다. 

 

- 계단의 값이 2인 경우 stare[1][0]의 값과 val[1]의 값을 더해준 값을 기록하고 1, 2 계단이 연속되고 있기 때문에 stare[2][1] = 2가 된다.

 

- 계단이 3개 이상인 경우 부터 분류를 시켜주는데 크게 두 가지로 분류했다.

 

1. 이전 계단이 연속된 상태인 경우(stare[i - 1][1] == 2)

 

이 경우 마지막 계단을 밟으면 연속 계단이 3이 되므로 i - 2 계단을 무조건 밟아야 한다고 생각했다. (그래서 무수한 틀림 발생)

 

그런데 곰곰이 생각해보니 i - 3 계단을 밟고 i - 1계단과 마지막 계단을 밟는 경우의 수도 있어서 이 두 개를 비교하고 큰 값을 stare[i]에 넣어줬다.

 

(앞의 경우 i - 2, i 연속되지 않은 계단을 밟았기 때문에 stare[i][1] = 1, 뒤의 경우 i - 3, i - 1, i 연속된 2개 계단을 밟았기 때문에 stare[i][1] == 2)

 

2. 이전 계단이 연속되지 않은 상태인 경우 (stare[i - 1][1] == 1) 

 

이 경우 그냥 i - 2와 i - 1 중 더 큰 값을 비교해서 그 값과 마지막 계단의 값을 더한 것을 stare[i][0]에 넣어줬다.

 

(앞의 경우 i - 2, i 연속되지 않은 계단을 밟았기 때문에 stare[i][1] = 1, 뒤의 경우 i - 1, i 연속된 2개 계단을 밟았기 때문에 stare[i][1] == 2)

 

 

 

 

풀이

N = int(input())
val = list()
for _ in range(N) :
    val.append(int(input()))

stare = [[0, 0] for _ in range(301)]
stare[1] = [val[0], 1]
if len(val) >= 2:
    stare[2] = [val[0] + val[1], 2]

if len(val) >= 3 :
    for i in range(3, len(val) + 1) :
        if stare[i - 1][1] == 2:
            another = val[i - 2] + stare[i - 3][0]
            if another > stare[i - 2][0] :
                stare[i] = [another + val[i - 1], 2]
            else :
                stare[i] = [stare[i - 2][0] + val[i - 1], 1]
        else :
            if stare[i - 1][0] > stare[i - 2][0] :
                stare[i] = [stare[i - 1][0] + val[i - 1], 2]
            else :
                stare[i] = [stare[i - 2][0] + val[i - 1], 1]

print(stare[len(val)][0])

 

 

 

 

결과