백준 2579 계단오르기 문제풀이

문제 

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

 

문제 접근 방식

i 번째 까지의 계단 총합의 최댓값이 이전 항들의 최댓값과 연관성이 있는 것 같고 이를 점화식으로 표현하여 dp로 풀려고 하였다.

이제 점화식을 구해보자.

 

 i 번째까지의 최댓값을 d[i] 라고 할 때, 한 번에 오를 때 1~2계단을 오를 수 있으므로 d[i-1] 과 d[i-2] 를 통해 점화식을 구할 수 있을 것 같다. 아래 처럼 점화식을 작성하면 될까?

 

d[ i ] = max( d[ i-1 ] , d[ i-2 ] ) + stairs[ i ]

 

이렇게 하면 오답이 된다. 문제에서 연속된 계단 3개를 오를 수 없다는 제한 사항이 있기 때문에 아래와 같은 상황이 있을 수 있다. 

 

그럼 어떻게 점화식을 표현할 수 있을까? 

연속된 세개의 계단은 오를 수 없다는 제한 때문에 i-3 번째도 같이 고려를 해서 점화식을 작성해야한다.

 

i-1, i-2, i-3 번째 계단을 통해 i 번째를 오르는 방법은 다음 두가지 뿐이라는 것을 알 수 있다.

1. i-3번째에서 i-1번째 계단을 오르고, i-1 번째에서 i 번째로 오르는 경우

2. i-2 번째에서 i 번째로 오르는 경우

 

1, 2번을 활용하면 경우의 수 중복 없이, 연속된 3개의 계단을 오를 수 없다는 규칙을 만족하며 계단을 오를 수 있다.

점화식을 작성하면 아래와 같다.

d[ i ] = max( d[ i-3 ] + stairs[i-1] , d[ i-2 ] ) + stairs[ i ] (  i 는 세 번째 계단 이상부터 가능 )

 

이 점화식을 활용하여 n번째 계단까지의 총합을 누적해서 계산하고, d[n] 을 반환하면 된다.

 

 

시간 복잡도

i를 n번째 까지 반복하기 때문에 O(n) 이 걸리며, n 의 최댓값이 300이기 때문에 시간 내에 동작함을 알 수 있다.

 

 

코드

import sys

if __name__=='__main__':
    n=int(input())
    stairs=list(map(int,sys.stdin.read().splitlines()))

    # 시작 위치의 값인 0 을 첫번째에 넣어줌
    stairs.insert(0,0)

    # i번째 까지의 총점수의 최댓값을 저장해놓는 리스트 생성 및 1,2,3항 값 설정
    d=[0]*(n+1)
    d[1] = stairs[1]

    if n>1:
        d[2]=stairs[1]+stairs[2]

        # n번째까지 순서대로 점화식을 이용하여 리스트 d에 총점수의 최댓값을 저장해나간다.
        for i in range(3,n+1):
            d[i]=max(d[i-3]+stairs[i-1], d[i-2])+ stairs[i]

    print(d[n])

 

 

회고

처음 제출할 때 index out of range 라는 에러가 발생하였는데, 점화식의 초기 항을 제대로 고려해주지 않아서 발생한 문제였다.

계단이 하나만 주어진 경우 (n=1), d[2] 에 접근하려 했기 때문에 에러가 발생했으며, 이를 조건문을 통해 해결하였다.

점화식의 경우 이전 항을 참조하여 문제를 풀기 때문에 초기항에 대한 예외 처리를 항상 고려해줘야한다.