[BOJ:2579] 계단 오르기

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

 

Note

도착점의 위치를 N이라고 할때 도착점에 도달 하는 최대를 구하는 방법은 마지막에 2칸을 이동하는 방법인, N-2까지 문제의 조건대로 최대 점수를 구하는 방법으로 온 다음 N으로 가는법과 마지막에 한 칸을 이동하는 방법인 ,N-3까지 문제의 조건대로 최대 점수를 구하는 방법으로 온 다음 N-1, N으로 오는 방법중 최대를 구하면 된다. 이때 후자의 경우 N-1까지 최대로 온 다음 N으로 가면 되지 않나 생각할 수 있는데 이렇게 되면 N-1까지 최대로 온 경우가 N-2를 통해서 왔는지 체크할 수 없기 때문에 안된다. 왜냐하면 N-1까지 오는 최대의 경우가 N-2를 거쳐서 왔다고 하면 N을 밟는 순간 3계단 연속 밟기 때문에 문제의 조건에 위배되기 때문이다.
그리고 이 경우를 구하기 위해 한 번의 N의 경우를 구할 수 없기 때문에 1,2부터 차례로 Bottom-up 방식으로 문제를 해결할 수 있다.
6개의 계단이 다음과 같이 있을 때를 생각해보자.
10,20,15,25,10,20
1과 2의 경우 직관적으로 10, 30(10+20)이 최대 점수다. 계단 3까지 오는 경우를 생각해보면 3개의 계단을 연속으로 오를 수 없기 때문에 1계단을 밟고 3계단을 오거나 2계단을 밟고 3계단을 와야하는데 2계단을 밟을 때는 1계단을 밟았으면 안된다.

점화식으로 표현하면 다음과 같다.
max_score[n] = max(stiar[n]+stair[n-1] + max_score[n-3], stair[n] + max_score[n-2])

Code