기록공간

동적계획법을 사용하는 문제였다. 우선 점화식을 찾기 위해 규칙이 어떠한지 부터 살펴보자. P(1)~P(3)일때는 1로 모두 동일하다. 그리고 P(4)~P(5)일때 2이다. P(4)의 값은 P(1)과 P(2)를 더하여 2가 나오며, P(5)의 값은 P(2)와 P(3)을 더하여 2가 나온다. P(6)의 값은 P(3)과 P(4)를 더하여 3이 나온다. 이러한 규칙을 봤을때 점화식은 다음과 같을 것이다. P[N] = P[N - 3] + P[N - 2] 결과값이 int의 범위를 넘어가기 때문에 P(N)의 값을 저장할 dp 테이블 배열을 long long 형식으로 선언해주어야 한다. 코드는 다음과 같다. #include using namespace std; int main() { long long dp[100 + ..