기록공간

동적계획법을 사용하는 문제였다. 규칙 계단을 오른때는 1칸 또는 2칸 오를 수 있다. 연속된 3칸을 오를 수 없다. 마지막 계단은 무조건 밟아야한다. 위 3가지 규칙을 바탕으로 마지막 계단을 밟는 경우를 두가지로 분류 해볼 수 있다. 1. 마지막 계단을 밟고 그 전 계단을 밟는 경우 (하지만 위 규칙 2번으로 인해 무조건 전 계단을 밟은 이후 전전전 계단을 밟아야 한다.) 이 경우 점화식은 S[n] = S[n] + S[n - 1]이 된다. (위 규칙 2번으로 인해 DP[n - 3]도 더해줘야 한다.) (S는 계단의 값들을 보관하는 배열이고 DP는 계단까지의 최대값을 보관하는 DP테이블(배열)이다.) 2. 마지막 계단을 밟고 그 전전 계단을 밟는 경우 이 경우 점화식은 S[n] = S[n] + DP[n -..