[백준 2579] 06 정올 초등부 "계단 오르기"

문제 출처 : https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

이 문제는 2006년 정보올림피아드 시. 도 지역 본선 초등부 4번 문제 입니다. 지금으로 따지면 1차 대회에서 초등부 가장 어려운 문제 였습니다. 지금이라면 2~3번 수준의 문제이지 않나 생각합니다. 시간이 흐르면 흐를수록 문제가 어려워지고 있는것 같습니다.

 

계단을 오르는 규칙을 지키면서 얻을 수 있는 점수의 최댓값을 구하는 문제 입니다. 이런 유형의 문제는 다이나믹 프로그래밍(DP)로 해결할 수 있습니다.

DP의 풀이 방법

DP는 크게 두가지 방식으로 풀 수 있습니다.

Top-Down

첫 번째는 Top-Down 방식 입니다. 위에서 아래로 떨어지듯이 큰 문제를 작은 문제로 바꿔 작은 문제를 풀고, 작은 문제를 푼 결과를 바탕으로 큰 문제를 해결하는 방식 입니다. 큰 문제를 해결하기 위해 재귀함수를 사용하여 작은 문제를 해결합니다. 이 방식은 쉽게 코드를 구성할 수 있지만 재귀를 사용하기 때문에 느리다는 단점이 있습니다.

Bottom-Up

다음으로 Bottom-Up 방식입니다. 작은 문제를 해결해 나가면서 큰 문제를 해결하는 방식 입니다. 작은 문제를 해결하는 방법은 점화식을 사용하여 문제를 해결하는 것입니다. 반복문을 사용하기 때문에 Top-Down에 비해 속도가 빠르다는 장점이 있습니다. 하지만 점화식을 찾기가 힘들다는 단점이 있습니다.

 

Top-Down DP 에 대해서 기억이 나지 않는다면 링크를 따라가 확인해 보길 바랍니다.

 

따라서 우리는 Top-Down으로 먼저 문제를 해결하고, 해결한 방식으로 점화식을 찾아 Bottom-Up으로 코드를 변경합니다. 이 문제는 Top-Down으로 풀어 보겠습니다. solve라는 함수를 만드는데 이 함수는 n개의 계단을 오르면서 얻을 수 있는 최대 점수를 얻는 함수라 생각하겠습니다.

 

입력 받기

N = int(input())

arr = []
for _ in range(N):
    arr.append(int(input()))

계단의 개수 N, 계단에 쓰인 점수를 arr이라는 리스트에 넣습니다.

출력하기

print(solve(N - 1))

solve(n)이라는 함수는 n 번째 계단에 얻을 수 있는 최대 점수를 리턴한다고 하였습니다. 이제 이 solve 함수를 만들어 보겠습니다.

solve 함수 만들기

계단 오르기에는 몇 가지 규칙이 있습니다.

1. 한 번에 한계단씩 또는 두 계단씩 오를 수 있습니다.
2. 연속된 세 개의 계단을 모두 밟으면 안됩니다.
3. 마지막 계단은 무조건 밟아야 합니다.

이 세 가지의 규칙이 있습니다. 이 규칙을 잘 적용해 보면 아래와 같은 두 가지 방식을 찾을 수 있습니다.

그럼 위의 그림에서 노란색 신발처럼 세 번째 계단에서 두 계단 오르고, 한 계단 오르는 방식이 있고, 연두색 신발 처럼 두 계단을 오르는 방식이 있습니다. 이렇게 이야기 하면 아래와 같은 빨간색 신발의 방법도 있다고 생각할 수 있습니다.

빨간색 신발의 방법이 안되는 이유는 바로 연속된 세개의 계단을 밟을 수 없다는 단서 떄문 입니다. 빨간색 신발의 방법을 사용하면 밑의 계단을 연속해서 몇 개나 밟았는지 계속 신경써야 합니다. 위의 노란색과 초록색의 방식은 시작 계단에서 다음 계단을 밟지 않고 두칸 건너 뛰어 버립니다. 이렇게 하면 세 계단을 밟는지 신경쓰지 않아도 됩니다. 이것을 코드로 작성해 보겠습니다.

계단 함수 만들기

def solve(n):
    case1 = solve(n - 2) + arr[n]
    case2 = slove(n - 3) + arr[n - 1] + arr[n]

    return max(case1, case2)

solve(n - 2)는 두 칸 밑에서 얻을 수 있는 최대 점수 입니다. 여기서 두 칸의 계단을 올라오는 방식이 첫 번째 case 입니다.

solve(n - 3)은 세 칸 밑에서 얻을 수 있는 최대 점수 입니다. 여기서 두 칸의 계단을 올라오고, 한 칸의 계단을 올라오는 것이 두 번째 case 입니다. 이 두가지 케이스의 최대값이 우리가 찾는 n번째 계단에서 얻을 수 있는 최대 점수 입니다.

종료 조건 추가하기

재귀함수에는 무조건 종료조건이 있어야 합니다. 종료조건이 없으면 무한 루프에 빠지게 되어 함수가 무한히 반복하게 됩니다.

def solve(n):
    if n == 0:
        return arr[0]
    if n == 1:
        return arr[0] + arr[1]
    if n == 2:
        return max(arr[0] + arr[2], arr[1] + arr[2])

    case1 = solve(n - 2) + arr[n]
    case2 = slove(n - 3) + arr[n - 1] + arr[n]

    return max(case1, case2)

n이 0인 경우는 첫 번째 계단인 경우 입니다. 따라서 첫 번째 계단의 값을 리턴해 줍니다.

n이 1인 경우는 첫 번째 계단과 두 번째 계단이 있는 경우 입니다. 두 개의 계단이 있기 때문에 두 계단을 모두 밟는 것이 최대 점수 입니다. 따라서 arr[0] + arr[1]로 두 개의 계단의 합을 리턴합니다.

n이 2인 경우는 처음부터 세 개의 계단이 있는 것입니다. 세 개의 계단을 모두 밟지 못하기 떄문에 첫 번째와 세 번째 계단의 합이나, 두 번째와 세 번째 계단의 합 중에 큰것을 리턴해 줍니다.

메모이제이션

Top-Down DP 문제를 해결할 때에는 메모이제이션에 신경써 주어야 합니다. 메모이제이션을 통해 이미 계산 완료한 부분은 더 이상 계산하지 않을 수 있도록 합니다.

memo = [0] * (N)

def solve(n):
    if n == 0:
        memo[n] =  arr[n]
        return memo[n]
    if n == 1:
        memo[n] = arr[n] + arr[n-1]
        return memo[n]
    
    if n == 2:
        memo[2] = max(arr[1] + arr[2], arr[0] + arr[2])
        return memo[n]

    if memo[n]:
        return memo[n]
    
    case1 = solve(n-2) + arr[n]
    case2 = solve(n-3) + arr[n-1] + arr[n]

    memo[n] = max(case1, case2)
    return memo[n]

memo[n]의 값이 존재하면 해당 값을 리턴해 주도록 하였습니다. 그리고 아직 값이 없다면 계산을 통해 memo[n]을 만들어 주었습니다. 

 

이렇게 간단한 DP 문제를 해결해 보았습니다. 이 방식으로 해결이 되지 않았다면 Bottom-Up 방식으로 코드를 변경해야 하지만, 여기서는 문제가 해결이 되었기 때문에 Bottom-Up으로 바꾸지는 않겠습니다.