BOJ_2579 : 계단 오르기

👉 문제링크

2579번: 계단 오르기

---

---

🔸 문제 분석 🔸

• 규칙에 따라 계단을 오르며 값의 총합이 최대가 되도록 한다.
  • 규칙1. 계단은 1칸 혹은 2칸(1칸 점프) 씩 오를 수 있다.
  • 규칙2. 연속된 3개의 계단을 연속으로 밟을 수 없다.
  • 규칙3. 마지막 계단은 반드시 밟아야 한다.
• DP 문제이고 마지막은 꼭 밟아야하기 때문에 거꾸로가는 점화식을 만들어본다.
  • 마지막 계단의 인덱스가 n이면, 밟을 수 있는 종류는 2가지다
    • 1) n과 n-1을 연속으로 밟는다 = n-2를 밟으면안된다 = n-3을 밟는다.
      • dp[n-3] + arr[n-1] + arr[n]
    • 2) n-1을 밟지 않는다.
      • dp[n-2] + arr[n]
    • 최대값을 찾아야 하므로, 두 방법 중 큰 걸 선택한다.
• 인덱스 0, 1, 2일때 점화식 1번이 적용이 안되므로 0, 1, 2는 따로 입력한다.
  • 1) 인덱스 0 선택 방법 1개
  • 2) 인덱스 1 선택 방법 2개 : max(arr[0] + arr[1], arr[1])
  • 3) 인덱스 2 선택 방법 2개 : max (arr[0] + arr[2], arr[1] + arr[2])
• n이 2이하일때도 따로 처리한다.

🔸 코드 🔸

n = int(input())

arr = []
dp = [0] * n

for _ in range(n):
    arr.append(int(input()))

dp[0] = arr[0]
if n == 1:
    print(sum(arr))
    exit(0)
dp[1] = max(arr[0]+arr[1], arr[1])
if n == 2:
    print(sum(arr))
    exit(0)
dp[2] = max(arr[0]+arr[2], arr[1]+arr[2])

for i in range(3, n):
    dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i])

print(dp[n-1])

🔸 코드 해석 🔸

• arr : 계단 값을 저장하는 리스트
• dp : 계산 결과를 저장하는 리스트 (인덱스마다 도착 시 최대값)
• n이 1, 2일때 예외처리
• 인덱스 0, 1, 2는 dp를 따로 계산
• 그 외에는 점호식대로 계산

---

🔸 end 🔸

• dp문제의 갈피를 못잡고 정답을 보게되었다. 보통 점화식을 세운다는 걸 기억했지만 이해하는데 오래걸렸다.
• 혼자 규칙을 생각할때도 n의 크기를 너무 작게 잡은게 흠이었다.
• 기본 규칙을 갖고 잘 유추할 수 있도록 해야겠다.
• dp문제는 더 연습해봐야겠다.