백준 2579번_계단 오르기 (Python)

바로가기

 

문제

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

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

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

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

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

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

*각 계단의 점수는 모두 자연수

 

코드

n = int(input())
stair = [None] * n
dp = [[None] * 2 for i in range(n)]
for i in range(n):
    stair[i] = int(input())
if n==1:
    print(stair[0])
else:
    dp[0][0] = stair[0]
    dp[0][1] = 0
    dp[1][0] = stair[1]
    dp[1][1] = stair[0]+stair[1]
    
    for i in range(2, n):
        dp[i][0] = max(dp[i-2][0], dp[i-2][1])+stair[i]
        dp[i][1] = dp[i-1][0]+stair[i]
    
    print(max(dp[n-1]))

 

풀이

이 게임의 규칙의 1, 2번은 다음과 같이도 요약이 가능하다.

1. 1칸을 오르거나 2칸을 오르는 것만 가능
2. 1칸 오르기 다음은 무조건 2칸 오르기여야 함

모든 경우의 수를 하나하나 다 따져보는 데는 현실적인 어려움이 있으므로 각 계단의 층에 대해서 점수의 최댓값을 구해가는 소문제의 DP로 나눌 것인데, 위의 규칙을 따르기 위해서 (계단의 층수)*2 크기의 2차원 배열을 만들 것이다.

 

위 코드에서 표현을 빌려오면 dp[i][j]에서 i가 층수, j가 가장 최근 이동이 1칸 오르기였는지 확인하는 값이다. j가 0이면 가장 최근 이동은 2칸 오르기였음을 나타내고, j가 1이면 가장 최근 이동이 1칸 오르기여서 바로 다음 이동은 무조건 2칸 오르기로 결정됨을 나타낸다.

 

그럼 i번째 계단을 생각하자. i번째 계단으로 가는 이동이 1칸 오르기였다면, i-1번째 계단에서 올라온 것은 자명하다. 이때 i-1번째 계단으로 간 이동도 1칸 오르기였다면 연속해서 1칸 오르기를 하여 i번째 계단에 가는 것은 규칙에 어긋나므로, i-1번째 계단으로 간 이동이 2칸 오르기였던 경우만 생각하면 된다. 위 코드의 표현을 빌리자면, dp[i-1][0]이 우리가 고려할 수 있는 유일한 경우가 된다.

반면, i번째 계단으로 가는 이동이 2칸 오르기였다면, 역시 i-2번째 계단에서 바로 올라온 것을 알 수 있다. 이때 i-2번째 계단으로 간 이동이 1칸 오르기였는지, 2칸 오르기였는지는 i번째 계단으로 가는 이동에는 영향이 없다. 2칸 오르기에는 제한이 없기 때문이다. 따라서 두 경우 중 점수가 더 높은 경우를 반영하여 i번째 계단의 점수를 결정해주면 된다.

 

그리고 코드에서 조금 디테일적인 부분으로, dp[0]과 dp[1]을 초기화 할 때, dp[0][1]은 첫번째 계단으로 갈 때 1단 오르기가 있었다는 뜻이다. 하지만 출발점은 계단으로 생각하지 않기로 했으므로 이 값은 존재하지 않는다. 그렇다고 이를 None으로 그대로 두면, for 반복문에서 i가 2가 될 때 자연수인 dp[0][0]과 None인 dp[0][1]인 둘을 비교하게 되는 상황이 벌어져 에러가 발생한다. 이를 처리하기 위해 어차피 둘 중 최댓값이 반영될 것이고, dp[0][0]은 자연수이므로 dp[0][1]을 모든 자연수보다 작을 0으로 설정해주면 어떤 상황이든 우리가 원하는 dp[0][0]이 반영될 것이다.