계단 오르기
BOJ 2579 계단 오르기
boj 2579 계단 오르기 문제의 조건에 따라 마지막 계단은 무조건 밟아야한다. 계단은 연속으로 두번까지 밟을 수 있다. 마지막 계단을 밟는데, 그 마지막 계단이 연속으로 밟은 첫번째 계단이냐 두번째 계단이냐로 경우의 수를 나눌 수 있다. 이를 바탕으로 테이블을 정의해보자. D[i][1] = 마지막 계단이 i번째 계단이고 1개의 계단을 연속으로 밟은 경우, 계단 점수 합의 최댓값 D[i][2] = 마지막 계단이 i번재 계단이고 2개의 계단을 연속으로 밟은 경우, 계단 점수 합의 최댓값 D[i][1]의 경우는 i-1번째 계단을 밟지 않으므로, 마지막 계단이 i-2번째 계단일 경우의 계단 점수의 최댓값에서 i번째 계단 점수를 더하면 된다. D[i][2]의 경우는 i-1번째 계단을 무조건 밟고, i-2번째 ..