[백준, 2579번] 계단 오르기 (다이나믹 프로그래밍 : DP, Java)

문제설명

입력 & 출력

나의 풀이

접근 방법

먼저 이번 "백준 - 계단 오르기" 문제는 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임입니다.

 

문제를 하나씩 살펴보면 문제는 규칙이 있고 이 규칙을 유지한채 각 계단의 최댓값을 구하면 되는 문제입니다.

• 계단은 1 칸과 2칸 만 오를 수 있다.
• 계단을 연속해서 3계단을 밟으면 안된다.
• 마지막 계단은 반드시 밟아야 한다.

따라서, 연속해서 3개의 계단을 밟을 수 없다는 제약을 고려하여, 각 계단을 오를 때 이전에 1칸을 올라왔는지, 아니면 2칸을 올라왔는지에 따라 최댓값을 구하는 방식으로 접근할 수 있습니다.

 

위와 같은 예제를 기준으로 각 계단이 갖는 최댓값을 구하면 다음과 같습니다.

	10	20	15	25	10	20
1 Jump	10	30	35	50	65	65
2 Jump	0	20	25	55	45	75

 

각 계단의 최댓값을 구할 때는 두 가지 경우(1칸 점프, 2칸 점프)를 고려해야 합니다. 따라서 이전에 계산한 값을 재활용해야 하므로, 다이나믹 프로그래밍을 사용하면 효율적으로 문제를 풀 수 있습니다.

[Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기

전체 코드

 

1. 이전 계단(i-1)을 밟았을 경우

• 이 경우, 연속된 세 계단을 밟을 수 없으므로 i-2는 건너뛰어야 합니다.
• 따라서 i-3에서 시작해야 하며, 점수는 다음과 같이 계산됩니다.
  • dp[i] = dp[i−3] + stairs[i−1] + stairs[i] 
• 즉, 세 계단 전에서 한 계단(i-1)을 거쳐 현재 계단(i)으로 오는 경로입니다.

2. 이전 계단(i-1)을 밟지 않았을 경우

• 이 경우, 두 계단 전(i-2)에서 현재 계단(i)으로 바로 이동할 수 있습니다.
• 점수는 다음과 같이 계산됩니다.
  • dp[i] = dp[i−2] + stairs[i]
• 즉, 두 계단 전에서 바로 현재 계단(i)으로 오는 경로입니다.

3. 점화식

• 최대 점수를 얻기 위해 두 경우 중 더 큰 값을 선택합니다.

dp[i] = max⁡(dp[i−2] + stairs[i] , dp[i−3] + stairs[i−1] + stairs[i])

 

 

4. 예외 처리

• 다이나믹 프로그래밍은 현재 상태를 이전 상태들로부터 계산하므로, 초기값이 정확히 설정되지 않으면 결과도 잘못될 수 있습니다.
• 계단의 개수가 작을 때는 점화식을 그대로 적용할 수 없으므로 별도의 예외 처리가 필요합니다.
• 따라서 계단의 수가 1과 2일 때는 점화식을 사용할 수 없으므로 예외처리가 필요합니다.