[BOJ] 2579

less than 1 minute read

계단 오르기

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

dp를 이용하는 문제입니다.
i번째 계단에 갈 때, i - 1번째 계단에서 왔을 경우와 i - 2번째 계단에서 왔을 경우를 구분하여 점화식을 구할 수 있습니다.

  1. i - 1번째 계단에서 왔다면 계단을 3칸 연속으로 밟을 수 없으니 i - 3번째 계단 또한 무조건 밟아야 합니다.
  2. i - 2번째 계단에서 왔다면 1번과 같은 제약사항이 없습니다.

이 두가지를 통해
dp[i] = max(stair[i - 1] + dp[i - 3] + stair[i], dp[i - 2] + stair[i])의 점화식을 도출하여 사용하면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/2579.cpp

Categories:

Updated:

Leave a comment