[Baekjoon]백준 2579 계단 오르기(실버 3) - Python

문제설명 1

문제설명 2

문제를 살펴보면 계단오르기 게임을 하되, 3개의 조건을 만족하는 최댓값을 찾아야한다

처음에 생각한 로직은 부분합 알고리즘을 활용하여 해당 칸에서 두번째 계단의 합과 첫번째, 세번째 계단의 합

중에서 더 큰 값을 저장하며 앞으로 한 칸 또는 두 칸씩 index를 전진하는 방향으로 생각하였다

그리고 이를 구현한 코드의 일부이다

if n == 1: # 계단이 하나인 경우
    print(stairs[0])
elif n == 2: # 계단이 두 개인 경우
    print(stairs[0] + stairs[1])
else:
    stairs[1] += stairs[0]
    
    i = 2
    while i < n-1:
        if stairs[i+2] >= stairs[i+3] + stairs[i+1]:
            stairs[i] += stairs[i+2]
            i += 2
        else: 
            stairs[i] += stairs[i+3] + stairs[i+1]
            i += 1
        print(f'Index : {i}')

    print(stairs[n-1])
    
print(stairs)

작성을 해보며 테스트 케이스를 입력하던 도중 index 오류가 자주 발생하였다

else문 밑의 첫번째 print문에서 볼 수 있듯 index값을 출력하도록 하였는데, i+3인 경우에 

stairs의 범위를 넘어가버리는 경우가 자주 일어났다 또한 부분합으로 구현하였더니 계산값이 정확하지 않았다

해당 조건들을 추가하여 다시 작성하기에는 추가적인 조건들이 너무 많아질 것 같아서 다른 방법을 생각해보았다

(추후에 해당 방법으로 해결하는 방법을 찾게 된다면 글을 수정하겠습니다)

 

동적 프로그래밍을 사용할 때 자주 사용되는 다른 하나의 리스트를 만들어

해당 계단의 값을 저장하는 로직으로 바꾸어서 다시 코드를 작성하였다

result[2]의 경우 시작점이 바닥이기 때문에 첫번째 계단과 세번째 계단을 밟은 경우, 

두번째 계단과 세번째 계단을 밟은 경우 중 최댓값을 저장해준다

(시작점이 바닥이라는 점을 제대로 확인하지 못해 오랜 시간을 뺏겼다...)

result[i-3] + stairs[i-1] + stairs[i]:

이 부분은 i-3번째 계단에서 시작하여 두 계단을 한꺼번에 올라온 뒤(i-3에서 i-1로) 계단을 연속으로 밟는 경로이며, 

result[i-2] + stairs[i]:

이 부분은 바로 두 계단을 올라 i번째 계단으로 올라오는 경로이다

그 중에서 최댓값을 찾아 result[i]에 저장하면 된다

n = int(input())
stairs = []

for _ in range(n):
    stairs.append(int(input()))

result = [0] * n
result[0] = stairs[0]
result[1] = result[0] + stairs[1]
result[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2])

for i in range(3, n):
    result[i] = max(result[i-3] + stairs[i-1] + stairs[i], result[i-2] + stairs[i])
    
print(result[n-1])

허나 해당 코드는 런타임에러(IndexError)가 발생한다

그래서 천천히 다시 살펴보면서 result의 index를 벗어나는 부분과 stairs의 index를 벗어나는 부분을 찾아보았다

for문 부분을 제일 유심깊게 살펴보았는데...이상한 부분이 보이지 않았다

그래서 잠시 머리 식히고 나중에 다시 보자말자 이상한 점을 찾을 수 있었다

result[0], [1], [2] 부분들을 정의하고 있으나 만약 n이 1이라면..?

result[1], [2]부분에서 indexError가 발생할 것이다 2인 경우에도 마찬가지로 result[2]부분에서 에러가 발생한다

 

그렇기 때문에 초반에 if문을 통해 n의 값에 따라 다른 동작을 취해주어야한다

수정한 후에 제출하면 정답임을 확인할 수 있다

n = int(input())
stairs = []

for _ in range(n):
    stairs.append(int(input()))

if n == 1:
    print(stairs[0])
elif n == 2:
    print(sum(stairs))
else:
    result = [0] * n
    result[0] = stairs[0]
    result[1] = result[0] + stairs[1]
    result[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2])

    for i in range(3, n):
        result[i] = max(result[i-3] + stairs[i-1] + stairs[i], result[i-2] + stairs[i])
        
    print(result[-1])