9461 : 파도반 수열 (Dynamic Programming) [C,C++]

DP의 기본 : 규칙 찾기

나선의 가장 긴 변의 길이는 어떻게 얻을까?

P(12)까지 전개해봤다.

P(1)

P(2)

P(3)

P(4)

P(5)

P(6)

P(7)

P(8)

P(9)

P(10)

P(11)

P(12)

전 개 식

1

1

1+1

2

2+1

3+1

4+1

5+2

7+2

9+3

12+4

16+5

가장 긴 변

1

1

2

2

3

4

5

7

9

12

16

21

여기서 구할 수 있는 점화식은

P(N) = P(N-5) + P(N-1)

무한히 전개해도 점화식이 맞는 것을 확인할 수 있다.

하지만 계속되는 사이트의 오답처리.. 무엇일까?

직접 실행해서 숫자를 돌려봤더니 int형의 범위 문제였다.

long long으로 변수형을 바꿔주고 실행했더니 정답!

Spiral::Spiral()
{
 this->DP[0] = 1; this->DP[1] = 1; this->DP[2] = 1;
 this->DP[3] = 2; this->DP[4] = 2;
 for (int i = 5; i < 100; i++)
 {
  this->DP[i] = this->DP[i - 1] + this->DP[i - 5];
 }
}

long long Spiral::Get(int n)
{
 return this->DP[n - 1];
}

<소스 코드>

*Source of the problem = https://www.acmicpc.net/problem/9461

*문제 출처 : BAEKJOON ONLINE JUDGE