백준_실버3_2579번(계단 오르기)

백준 문제링크
해당 문제는 다이나믹 프로그래밍 알고리즘을 사용하여 푸는 문제이다.

문제 이해

해당 문제의 기능 요구사항은 아래와 같다.

1. 계단은 한 계단 혹은 두 계단씩 오를수 있다.
2. 연속된 3개의 계단을 밟으면 안된다.
3. 마지막 도착 계단은 꼭 밟아야 된다.

문제 첫번째 시도 정리

문제풀이 첫번째 시도에서 2번 요구사항에 집중해서 3번를 신경쓰지 못하고 아래와 같이 코딩하였다.

def dp1(n, stairs):
    scores = stairs[:]
    for step in range(1, n + 1):
        beforeOneStep = step - 1
        beforeTwoStep = step - 2
        if step == 1:
            scores[step][1] += 1
        else:
            if scores[beforeOneStep][1] < 2 and scores[beforeOneStep][0] > scores[beforeTwoStep][0]:
                # 1계단 업
                scores[step][0] += scores[beforeOneStep][0]
                scores[step][1] = scores[beforeOneStep][1] + 1
            else:
            	# 2계단 업
                scores[step][0] += scores[beforeTwoStep][0]
                scores[step][1] = 1

    print(scores[-1][0])

위의 코드는 2번 요구사항인 연속된 계단을 피하면서 최대점수가 되도록 코딩하였다. 특이점은 해당 계단에 올라가기 전에 전 계단에서 연속된 계단을 탔는지 안탔는지 확인하도록 리스트에 추가하여 이를 구현하였다.
이 코드의 문제점은 만약, 최대값대로 계산하였지만 마지막 계단을 밟지 못할수 있다는 문제점이 있다(요구사항 3번 오류).
요구사항 3번까지 구현하기 위해 다른 방식으로 해결하고자 하였다.

문제 두번째 시도

3번 요구사항에서 마지막 계단을 꼭 밟아야 함으로 꼭 한 계단씩 오를 때 점수만 볼 것이 아니였다. 그래서 마지막 계단을 밟을 때 어떠한 케이스가 있는지 아래와 같이 분석해보았다.

CASE1 : 마지막 계단에서 한 계단 아래있을 때
CASE2 : 마지막 계단에서 두 계단 아래있을 때

CASE1과 CASE2에 따라서 구현할 때 아래와 같은 유형으로 계단을 타야됨을 알 수 있다. 예시로 계단이 4개일 때를 아래와 같이 구현하였다. 위는 CASE1일때, 아래는 CASE2일때다.

위의 그림을 보듯이 CASE1일때 파란색 계단을 꼭 거쳐야 하고 요구사항2번(연속된 3계단X)을 구현하기 위해 빨간색 화살표처럼 계단을 건너야 한다.
CASE2일때는 CASE1과 마찬가지로 파란색 계단을 꼭 거쳐야 함으로 위와 같이 건너야 한다.

첫 번째 계단은 첫번째 계단만큼의 점수가 되고 두 번째 계단은 첫 번째 계단과 두 번째 계단의 합이 점수가 될것이다. 그리고 세 번째 계단은 첫번째 계단과 세 번째 계단의 합이나 두 번째 계단과 세 번째 계단의 합 중 큰 것이 될 것이다. 네 번째 계단부터는 CASE1과 CASE2로 나눠 생각하고 차례대로(4~마지막 계단) 구하면 풀이가 될 것이다.

전체 코드

def dp2(n, stairs):
    scores = [0 for _ in range(n + 1)]
    if n == 1:
        print(stairs[1])
        return
    elif n == 2:
        print(stairs[1] + stairs[2])
        return
    elif n == 3:
        print(max(stairs[1] + stairs[3], stairs[2] + stairs[3]))
        return
    scores[1] = stairs[1]
    scores[2] = stairs[1] + stairs[2]
    scores[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])
    for step in range(4, n + 1):
        # case1 : ENDPOINT - 1
        case1 = scores[step - 3] + stairs[step - 1] + stairs[step]
        # case2 : ENDPOINT - 2
        case2 = scores[step - 2] + stairs[step]
        scores[step] = max(case1,case2)
    print(scores[-1])

def solution():
    n = int(input())
    stairs = [0]
    for _ in range(n):
        stairs.append(int(input()))
    dp2(n, stairs)

solution()