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

문제

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

2579번: 계단 오르기

 

문제 풀이

dp[n] : n번째까지의 계단 최댓값으로 설정하고 dp테이블을 채웠다.

최대 다음다음 계단까지 갈 수 있기 때문에 현재의 dp[n]은

1) dp[n] = dp[n-2] + A[n]

2) dp[n] = dp[n-1] + A[n]

둘 중 하나가 될 것이다.

 

그런데 연속해서 3개의 계단을 밟을 수 없기 때문에

이전 선택에서 2번을 선택했다면 무조건 1번을 선택해야 할 것이다.

 

그런데 또 여기서 반례가 있는데

2번을 선택했을 시 1번이 항상 최선이 아니라

dp[n-3] + A[n-1] + A[n] 이 최댓값이 될 수도 있기 때문이다.

 

예시로 문제의 예제를 dp테이블로 나타내면

A	10	20	25
DP	10	30	35

인데 dp테이블의 3번째 행의 경우를 보면

dp[n-2] + A[n]이 최선이 아니라 dp[n-3] + A[n-1] + A[n] 이 최선임을 볼 수 있다.

 

따라서

1) dp[n] = dp[n-2] + A[n]

2) dp[n] = dp[n-1] + A[n]

둘 중 더 큰 값을 택하되 만약 이전 선택에서 2번을 택했다면

1) dp[n] = dp[n-2] + A[n]

2) dp[n] = dp[n-3] + A[n-1] + A[n]

중에서 더 큰 값을 선택해서 dp를 채우게 했다.

 

length = int(input())
A=[0]
for i in range (length):
    A.append(int(input()))

dp=[0]*(length+1)
dp[1]=A[1]
dp[2]=A[1]+A[2]
continuous = True

for n in range(3,length+1):
    if(continuous):
        if(dp[n-2]+A[n]>dp[n-3]+A[n-1]+A[n]):
            dp[n] = dp[n-2]+A[n]
            continuous =False
        else:
            dp[n]=dp[n-3]+A[n-1]+A[n]
            continuous =True

    else:
        if(dp[n-2] +A[n]>=dp[n-1]+A[n]):
            dp[n]=dp[n-2] +A[n]
            continuous =False
        else:
            dp[n]=dp[n-1] +A[n]
            continuous =True

플래그 변수로 연속된 선택을 했는지 체크하고 분기를 나눴다.

그런데 이 코드 그대로 돌리면...

런타임 에러가 났다.. ^____^

 

질문 게시판좀 뒤져보니깐

n이 300 이하의 자연수 이기에

n이 1이 나오면 인덱스 범위 초과가 나올 수 밖에 없다.

 

그래서 n이 1일때 또 분기를 나눴다..

length = int(input())
A=[0]
for i in range (length):
    A.append(int(input()))

dp=[0]*(length+1)
dp[1]=A[1]
if(length==1):
    print(dp[length])
    
else:
    dp[2]=A[1]+A[2]
    continuous = True

    for n in range(3,length+1):
        if(continuous):
            if(dp[n-2]+A[n]>dp[n-3]+A[n-1]+A[n]):
                dp[n] = dp[n-2]+A[n]
                continuous =False
            else:
                dp[n]=dp[n-3]+A[n-1]+A[n]
                continuous =True

        else:
            if(dp[n-2] +A[n]>=dp[n-1]+A[n]):
                dp[n]=dp[n-2] +A[n]
                continuous =False
            else:
                dp[n]=dp[n-1] +A[n]
                continuous =True

    print(dp[length])

답은 맞았지만 다른 사람 코드를 좀 보니

굳이 분기를 나누지 않고 

dp[n] = max(dp[n-2]+A[n], dp[n-3]+A[n-1]+A[n])

이렇게 짜기도 하던데..

 

생각해보니깐 어차피 dp[n-2]+A[n]가 아니라 연속하게 선택을 하는 경우라면

무조건 dp[n-3]+A[n-1]+A[n] 이런 케이스기 때문에

굳이 복잡하게 분기를 나눌 필요가 없었다는 생각이 들었다..

다음엔 좀 더 잘 짜야겠다 ^_^