위의 설명을 보자마자 규칙이 너무 명확히 보였습니다. dp[n] = dp[n - 2] + dp[n - 3]을 점화식으로 둡니다.
N이 100이 들어왔을 때의 결과값이 int형 범위를 초과하기 때문에 long long 으로 타입을 변경했습니다. 이때 위의 점화식의 문제인줄 알고 dp[n] = dp[n - 5] + dp[n - 1]로 점화식을 변경했습니다.
문제를 풀고 다음날인 2월 24일. @suhshin과 @jseo와 얘기를 나눈 결과
dp[n] = dp[n - 1] + dp[n - 5]인 경우에는 삼각형의 빗변에 인접해 있는 두 삼각형 빗변들의 길이 합이고,
dp[n] = dp[n - 2] + dp[n - 3]인 경우에는 삼각형의 빗변을 평행 사변형으로 확장했을 경우에 두 삼각형 빗변 길이들의 합이 됩니다.
N의 값이 크지 않고 테스트케이스마다 값이 들어오므로, 미리 배열에 할당해 놓은다음 인덱스 접근하는 방법을 택했습니다.