백준 2579 - 계단 오르기

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

2579번: 계단 오르기

 

이 문제는 dp로 풀이하는건 알았는데 규칙을 못 찾아서 풀이하지 못했다.

dp리스트에 각 계단까지의 최대 점수값을 구하여 넣으면 된다.

 

문제의 제약 조건은 다음과 같다.

1. 계단은 한 번에 한 개 or 두 개씩 오를 수 있다.

=> 연속해서 3개는 불가능

2. 마지막 도착 계단은 반드시 밟아야 한다.

 

풀이코드 리뷰)

n = int(input())
st = []
dp = [0 for i in range(n)]

for i in range(n):
    st.append(int(input()))

if n >=3:
    dp[0] = st[0]
    dp[1] = dp[0] + st[1]
    dp[2] = max(st[1]+st[2], st[0]+st[2])

    for i in range(3, n):
        dp[i] = max(dp[i-3]+st[i-1]+st[i], dp[i-2]+st[i])

    print(dp[n - 1])
else:
    print(sum(st))

 

주의할 점)

마지막 계단은 반드시 밟는다는 조건이 있으므로, dp의 각 원소는 각 계단을 밟았을 때의 최대 점수가 된다.

=> 각 계단을 밟기 위해서는 어떻게 해야될까?

이 문제의 제약조건에 따른 두 가지 경우의 수가 있다.

1. 전전전 계단을 밟은 다음 + 바로 이전 계단을 밟고 + 현재 위치의 계단을 밟는 것

2. 전전 계단을 밟은 다음 + 현재 위치의 계단을 밟는 것

 

1번과 2번의 맨 앞에 써있는 ~계단을 밟은 다음 ~ 은

==> 결국, 그 전까지의 그 계단을 밟았을 떄의 최대 점수값을 뜻하며, 

이 문제의 최종목적은 최대점수값을 구하는 것이므로 1번과 2번 사이에서 최대만 저장해주면 된다.

 

==> 그럼 결국, dp리스트의 맨 마지막인 n-1번째 원소에는

가장 마지막 계단을 밟았을 때의 최대점수값이 들어가게 된다.

 

마지막 계단은 반드시 밟는다는 조건으로 dp의 각 원소는 각 계단을 밟았을 때의 최대 점수를 저장할 생각을 하지 못했다.

왜냐하면, 마지막 계단까지의 최대 점수는 중간에 있는 계단을 굳이 밟지 않고도 나올 수 있기 때문이다.

하지만, 마지막 계단을 밟기 위해서는 마지막의 전전전 계단 or 마지막의 전전 계단을 반드시 밟아야 마지막 계단을 밟을 수 있기 때문에 사실상 마지막 계단을 반드시 밟기 위해서는 반드시 밟아야 할 중간 계단들이 필수로 존재한다.

따라서, 중간에 있는 계단까지의 최대점수를 구할 때에도 계속 이러한 알고리즘을 적용시켜야 한다.

 

주의할 점)

입력받는 계단의 갯수가 3보다 작을 경우, 마지막 계단까지의 최대 점수는 입력받은 계단의 모든 점수를 합친 값이기 때문에 조건문을 걸어야 한다. 그러지 않을 경우, 초기화하는 부분에서 인덱스 에러(index error)가 발생한다.

 

느낀점)

문제는 이해하기 쉬운 것 같았는데 그 속의 규칙을 찾아서 코드로 구현해내는 것이 매우 어려웠던 문제였다.

dp는 구현하기는 쉽지만, 그 속의 원리를 가지고 점화식을 세우는 것이 어렵다고 생각한다.

이 문제는 반복문을 3부터 돌려서 결국 첫 번째와 두 번째까지는 직접 값을 넣어줬어야 됐는데, 자꾸 반복문을 첫 번째나 두 번쨰부터 돌려야지라는 고정관념을 가지고 접근한 것이 편협한 생각만 하는데 어느 정도 영향을 주었다고 생각했다.

너무 코드를 간결화하기 위해 전체를 일반화할 생각말고 차근차근 처음부터 끝까지 써보고, 일반화해보는 연습을 해야겠다.