2579

백준 2579 풀이 (다이나믹 프로그래밍, bottom-up, 계단 오르기)

이번 문제는 매번 그렇듯이 나에게 상당히 어려웠다. 재귀로 풀면 안된다는 느낌은 단박에 왔고, 다이나믹 프로그래밍을 써야한다는 느낌이 들었다. 물론 어떻게 써야할지 몰라서 문제였다. 그래서 다이나믹프로그래밍의 강좌를 듣고 bottom-up형식으로 풀어야한다는 것을 알게 되었다. bottom-up이란 작은 문제부터 풀어나가면서 결과를 저장시켜서 for 구문을 사용하여 푸는 방식이다. 일단 계단 오르기의 규칙은 다음과 같다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 여기서 중요한 ..