[백준] 2579 : 계단 오르기 / python

1. 문제 설명

2579번: 계단 오르기

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

 

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

 

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

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

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

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

입력

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

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

출력

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

 

2. 풀이 전 계획과 생각

입력

• N → 계단의 개수
• stairs_score → 각 계단에 쓰여있는 점수들 (1차원 배열)

 

문제 조건

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

• 지금까지 고려한 숫자의 위치를 알아야 한다.
• 그리고 연속된 세개의 계단을 모두 밟아서는 안된다는 조건이 있다.
  ⇒ 지금까지 연속해서 몇개의 계단을 밟았는지 알아야 한다.

 

점화식

• 문제 정의
  dp[i][j]에 대한 정의를
  'i번째 계단까지 고려했고, 현재 연속해서 j개 계단을 밟았다고 했을 때, 얻을 수 있는 최대 결과'라고 정의하자.
• 최종적으로 구하고자 하는 바
  max(dp[N][1], dp[N][2])
• 점화식 정의
  • 연속해서 몇개의 계단을 밟아왔는지에 따라 다르게 처리해주어야 한다.
    
    • 연속해서 2번째면, 이전 연속해서 첫번째에 지금 계단 점수를 더한다.
      dp[i][j] = dp[i - 1][1] + stairs_score[i]
    • 연속해서 첫번째면, 이이전 연속 2번째와 연속 1번째 중 최댓값에서 지금 계단 점수를 더한다.
      dp[i][j] = max(dp[i - 2][1], dp[i - 2][2]) + stairs_score[i]
• base 조건
  • 마지막 도착 계단은 반드시 밟아야 한다.
  • dp[1][1] = stairs_score[1]
  • dp[2][1] = stairs_score[2]
  • dp[2][2] = stairs_score[1] + stairs_score[2]

 

3. 풀이

N = int(input())
stairs_score = [0] * (N + 1)
 for i in range(1, N + 1):
     stairs_score[i] = int(input())

 dp = [[0] * 3 for _ in range(N + 1)]
 dp[1][1] = stairs_score[1]
 if N >= 2:
     dp[2][1] = stairs_score[2]
     dp[2][2] = stairs_score[1] + stairs_score[2]

 for i in range(3, N + 1):
     for j in range(1, 3):
         if j == 2:
             dp[i][j] = dp[i - 1][1] + stairs_score[i]
         elif j == 1:
             dp[i][j] = max(dp[i - 2][1], dp[i - 2][2]) + stairs_score[i]

print(max(dp[N][1], dp[N][2]))

 

4. 다른 풀이

N번째 계단에 도착하여 얻는 최대점수

dp[i][0] : i-1번째 계단을 밟지 않고, i번째 계단에 도착하여 얻는 최대 점수

dp[i][1] : i-1번째 계단을 밟고서, i번째 계단에 도착하여 얻는 최대 점수

 

구하고자 하는 값 max(dp[N][0], dp[N][1])

dp[1][0] = 10

dp[2][0] = 20

dp[2][1] = 30

n = int(input())
a= [0] * n
for i in range(n):
    a[i] = int(input())

dy = [[0, 0] for _ in range(n + 2)]

# 초기값 채우기
dy[0][0], dy[0][1] = 0, a[0]

if n >= 2:
    dy[1][0], dy[1][1] = a[1], a[0] + a[1]

# 점화식을 토대로 dy 배열 채우기
for i in range(2, n):
    dy[i][0] = max(dy[i - 2][0] + a[i], dy[i - 2][1] + a[i])
    dy[i][1] = dy[i - 1][0] + a[i]

print(max(dy[n - 1][0], dy[n - 1][1]))

 

5. 풀이 후 알게된 개념과 소감

• 작은 문제에서 큰 문제로 풀기 위해서는 문제 조건에 따라 충분한 정보가 필요하다.
  그러기 위해서는 상태값을 정의하면 된다.