백준 - 계단 오르기[2579]

이번 포스팅에서는 백준 알고리즘의 계단 오르기[2579] 코딩테스트 연습 문제를 풀어봅니다.

문제 설명

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

입출력 예

입력	출력
6 10 20 15 25 10 20	75

문제 풀이

동적계획법의 Top Down 방식을 이용하여 문제를 풀이 해보겠습니다.

예제의 입력을 다음과 같이 리스트로 표현할때 data = [10, 20, 15, 25, 10, 20] 이면 3번째 규칙에서 마지막 도착 계단은 반드시 밟아야 함으로 시작 계단의 점수는 마지막 n=5 번째인 20이 됩니다.

2번째 규칙에서 연속된 세 개의 계단을 밟아서는 안됨으로 n=3 ~ n=5 까지의 계단 [25, 10, 20]은 밟을 수 없으며

1번째 규칙에서 최대 밟을 수 있는 계단 수는 두 계단 까지 임으로 n=2 에서 n=5 [15, 20]은 밟을 수 없습니다.

그래서 n=5 계단에서 다음 밟을 계단은 n=4 10인 경우와 n=3 25인 경우로 나눌 수 있습니다.

n=5부터 전과 전전의 경우를 탐색 하는 방식을 트리로 표현하면 아래와 같습니다.

n=5 부터 n=0에 도달 할때 까지 경우의 수를 나누었습니다. 여기서 2번째 규칙인 연속된 세 개의 계단을 밟으면 안되는 조건을 뺴면 아래와 같습니다.

최종적으로 4개의 경우의 수 [10, 20, 25, 20], [10, 15, 25, 20], [10, 15, 10, 20], [20, 15, 10, 20]일 경우가 나오며 이중 합이 제일 큰 경우의 수 sum([10, 20, 25, 20]) => 75가 정답이 됩니다.

이를 코드로 구현하겠습니다.

stair = [10, 20, 15, 25, 10, 20]

def solution(n, p, c):
    if p - n == 1: # 호출한 계단이 인접 계단일 경우
        c += 1 # 카운트 증가
    if c == 3: # 연속된 세 개의 계단을 밟으면
        return 0 # 합계 0을 반환

    if n == 0: # 더 이상 계단이 없을때
        return 0
    elif n == 1: # 첫번째 계단일 때
        return stair[n-1]
    else: # 확인 할 계단이 남았을 때 제귀함수를 수행하고 수행이 종료 되면 두 비교 대상중 큰 값을 부모의 값과 더하여 반환
        return stair[n-1] + max(solution(n-2, n, c), solution(n-1, n, c))

print(solution(len(stair), 0, 1))

75

마지막으로 백준 문제에 맞게 입력을 받아서 처리하도록 수정 합니다.

from sys import stdin

stair_len = int(stdin.readline())
stair = []
for i in range(stair_len):
    stair.append(int(stdin.readline()))

def solution(n, p, c):
    if p - n == 1: # 호출한 계단이 인접 계단일 경우
        c += 1 # 카운트 증가
    if c == 3: # 연속된 세 개의 계단을 밟으면
        return 0 # 합계 0을 반환

    if n == 0: # 더 이상 계단이 없을때
        return 0
    elif n == 1: # 첫번째 계단일 때
        return stair[n-1]
    else: # 확인 할 계단이 남았을 때 제귀함수를 수행하고 수행이 종료 되면 두 비교 대상중 큰 값을 부모의 값과 더하여 반환
        return stair[n-1] + max(solution(n-2, n, c), solution(n-1, n, c))

print(solution(stair_len, 0, 1))

하지만 결과는….

다시 처음 부터 차근 차근 생각 해 봐야 할 거 같습니다. ㅠㅠ 2가지 경우를 생각하면 다음과 같습니다.

1. 밟은 계단이 마지막 - 1 일 경우 반드시 마지막 - 2 계단을 밟으면 안 된다.
2. 밟은 계단이 마지막 - 2 일 경우 그 전 계단은 신경 쓰지 않는다.

[10, 20, 15, 25, 10, 20]

n=0 [10]
새로 추가된 값은 꼭대기 위치 임으로 항상 더함 10
10

n=1 [10, 20]
새로 추가된 값은 꼭대기 위치 임으로 항상 더함 + 20
이전 값이 10만 있음으로 10을 더함 + 10
20 + 10 = 30

n=2 [10, 20, 15]
새로 추가된 값은 꼭대기 위치 임으로 항상 더함 + 15
연속된 세 개의 계단을 밟을 수 없음으로 20과 10중 큰 값인 20을 더함 + 20
15 + 20 = 35

n=3 [10, 20, 15, 25]
새로 추가된 값은 꼭대기 위치 임으로 항상 더함 + 25
‘마지막 -1’ 인 15의 계단을 밟을때 ‘마지막 -2’의 계단을 밟으면 안되고 그 이전인 n=0 일때 최대 값을 더해 줍니다. 15+10
‘마지막 -2’ 인 20의 계단을 밟을경우 그 전 계단은 신경 쓰지 않아도 됨으로 n=1 일때 최대 값을 더해 줍니다. 30
두 합 25와 30중 더큰 30과 꼭대기 위치 값 25를 더해 결과는 30 + 25 = 55

n=4 [10, 20, 15, 25, 10]
새로 추가된 값은 꼭대기 위치 임으로 항상 더함 + 10
‘마지막 -1’ 인 25의 계단을 밟을때 ‘마지막 -2’의 계단을 밟으면 안되고 그 이전인 n=1 일때 최대 값을 더해 줍니다. 25+30
‘마지막 -2’ 인 15의 계단을 밟을경우 그 전 계단은 신경 쓰지 않아도 됨으로 n=2 일때 최대 값을 더해 줍니다. 35
두 합 55와 35중 더큰 55와 꼭대기 위치 값 10를 더해 결과는 55 + 10 = 65

n=5 [10, 20, 15, 25, 10, 20]
새로 추가된 값은 꼭대기 위치 임으로 항상 더함 + 20
‘마지막 -1’ 인 10의 계단을 밟을때 ‘마지막 -2’의 계단을 밟으면 안되고 그 이전인 n=2 일때 최대 값을 더해 줍니다. 10+35
‘마지막 -2’ 인 25의 계단을 밟을경우 그 전 계단은 신경 쓰지 않아도 됨으로 n=3 일때 최대 값을 더해 줍니다. 55
두 합 45와 55중 더큰 55와 꼭대기 위치 값 20를 더해 결과는 55 + 20 = 75

이제 드디어 점화 식을 구성 할 수 있을거 같습니다. 메모이제이션 배열을 구성하여 n번째 까지 계산 했을때 가장 큰 경위의 값은

” memo(n) = max(stair[n-1]+memo(n-3), memo(n-2)) + stair[n] “

이제 위의 식을 코드로 구현 하겠습니다.

data = [0, 10, 20, 15, 25, 10, 20]

def solution(N, stair):
    if N == 1:
        print(stair[1])
    else:
        memo = {0: 0, 1: stair[1], 2: stair[1] + stair[2]}
        for i in range(3, N + 1):
            memo[i] = max(memo[i - 3] + stair[i - 1], memo[i - 2]) + stair[i]
        print(memo[N])

solution(len(data)-1, data)

75

다시 백준 문제에 맞게 입력을 받아서 처리하도록 수정 합니다.

from sys import stdin

# 입력
N = int(stdin.readline())
stair = [0]
for _ in range(N):
    stair.append(int(stdin.readline()))

if N == 1:
    print(stair[1])
else:
    memo = {0:0, 1:stair[1], 2:stair[1] + stair[2]}
    for i in range(3, N+1):
        memo[i] = max(memo[i-3] + stair[i-1], memo[i-2]) + stair[i]
    print(memo[N])

결과는 아래와 같이 잘 통과 되는 것을 확인 할 수 있습니다.