[java] 백준/2579 계단오르기문제

이 문제의 유형은 다이나믹프로그래밍이다.

다이나믹프로그래밍 문제를 풀때는 규칙을 찾아야하는데 ...

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

세가지 규칙으로 보면 결국 한칸씩 두번을 이동못한다는 얘기다.

1차원 배열과 2차원 배열 두가지로 풀수 있는데 이건 문제푸는 스타일에 맞춰서 푸시면된다.

마지막 도착 계단은 반드시 밟아야 한다...를 인용하면

dp[n] = dp[n-2] + stair[n] or dp[n-3]+stair[n-1]+stair[n]

이렇게 된다.

dp[n-2]+stair[n] 일 경우는 2칸씩 뛰어서 마지막 도착 계단을 밟을 경우고

dp[n-3]+stair[n-1]+stair[n] 일 경우는 1칸씩 뛰어서 마지막 도착 계단을 밟을 경우다.

 

2차원 배열로 풀 경우엔 dp[n][0] -> 한칸씩 이동할 경우 dp[n][1] -> 두칸씩 이동할 경우다.

dp[n][0] = dp[n-1][0]+stair[n] 한칸씩 이동할 경우 그전에 두칸을 뛰어오르고 한칸씩 이동하는 경우 하나다

dp[n][1] = dp[n-2][0]+stair[n] or dp[n-2][1]+stair[n] 두칸씩 이동할 경우는 그전에 한칸을 올랐던 두칸을 올랐던 둘다 가능하다.