계단 오르기 [백준 2579] - python

 

# 풀이 1번
import sys
input = sys.stdin.readline


def BOJ2579():
  n = int(input())
  stairs = [0 for _ in range(301)]
  for i in range(n):
    stairs[i] = int(input())

  dp = [0 for _ in range(301)]
  dp[0] = stairs[0]
  dp[1] = stairs[0] + stairs[1]
  dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2])

  # 마지막 칸은 꼭 밟아야 한다. 전칸을 밟을 경우와 밟지 않은경우가 있을것이다.
  for i in range(3, n) :
    dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])

  print(dp[n-1])
BOJ2579()

1번 풀이

 

1. 1단계와 2단계의 dp를 업데이트 해주었다.

2. 점화식을 세우기 위해 고심하던 중 마지막 칸은 꼭 밟아야 하는 조건을 계속 고려하려고 하였다.

3. 마지막 칸을 밟게 되면 전칸을 밟은 경우 vs 전칸을 밟지 않은 경우가 존재할 것으로 판단하였다.

4. 전칸을 밟게 되는 경우는 연속해서 3칸을 밟을 수 없는 조건이 있으므로 3번째 전칸의 최댓값 + 전칸, 현재칸을 더해주어야 한다.

5. 전칸을 밟지 않는 경우는 2칸전의 최댓값과 현재칸을 더해주면 된다.

6. 3칸 전의 최댓값을 고려해주어야 하므로 dp 배열에서 3단계를 업데이트 해주었다. 

 

 

 

# 풀이 2번

import sys
input = sys.stdin.readline

def BOJ2579() :
  n = int(input())
  stairs = []
  for _ in range(n) :
    stairs.append(int(input()))
  
  dp = [[0 for _ in range(3)] for _ in range(n + 1)]
  # dp[i][0] => 해당 칸을 안밟음
  # dp[i][1] => 해당 칸을 처음 밟음
  # dp[i][2] => 해당 칸을 연속해서 밟음 (i-1)번째를 밟았음

  for i in range(1, n+1) :
    dp[i][0] = max(dp[i-1][1], dp[i-1][2])
    dp[i][1] = dp[i-1][0] + stairs[i-1]
    dp[i][2] = dp[i-1][1] + stairs[i-1]
  
  print(max(dp[n][1], dp[n][2]))

BOJ2579()

2번 풀이

 

1. 한 칸에는 3개의 조건이 들어갈 수 있다. 

• 해당 칸을 밟지 않은 경우
• 전 칸을 밟지 않고 해당 칸을 밟은 경우
• 전 칸을 밟고 해당 칸을 밟은 경우

2. 위 조건을 기준으로 점화식을 세우려 했다.

3. 가장 헷갈렸던 부분은 한칸 띄고 밟게 되는 경우와 한 칸을 밟게 되는 경우 모두를 고려해줄 수 있는지 였는데 
전 칸을 밟지 않은 경우는 한칸 띄고 밟게 되는 경우고 이전에 밟았으면 연속으로 밟게 되는 경우이다.

4. 마지막 칸을 무조건 밟아야 하므로 전칸을 밟은 경우와 밟지 않은 경우 에서 최댓값을 출력해주면 된다.

 

 

 

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기