기본 콘텐츠로 건너뛰기

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
라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

11004 : K번째 수 [C++]

# include < iostream > # include < cstdio > # include < algorithm > int main ( ) { int * Number = new int [ 5000000 ] ; int N , K ; scanf ( " %d %d " , & N , & K ) ; for ( int i = 0 ; i < N ; i + + ) scanf ( " %d " , Number [ i ] ) ; std :: sort ( Number , Number + N ) ; printf ( " %d " , Number [ K - 1 ] ) ; return 0 ; }
댓글 쓰기
자세한 내용 보기

1149 : RGB Street Coloring (Dynamic Programming) [C,C++]

The key to this problem lies in understanding the principles. Let me explain the algorithm to solve the problem by using DP. First, you need the same storage space like input data's size. When you draw any color of the nth house, the space will contain the minimum value. If you paint the red in the second house, this value is sum of blue or green of the first house.  You must use DP because you must use the previous value.  Of course, you can also use the recursive algorithm to solve it. But if it gets bigger, it will take a lot of time.  If you paint the red in the nth house in the same way, you should add the lower value of the blue and green of the n-1th house.  Therefore, the minimum value can be found in the value of the storage space (n-1) index. <pesudo code> *Source of the problem =  https://www.acmicpc.net/problem/1149 *문제 출처 : BAEKJOON ONLINE JUDGE
댓글 쓰기
자세한 내용 보기

11478 : 서로 다른 부분 문자열의 개수 (미제) [C++]

# include < iostream > # include < vector > # include < string > using namespace std ; int main ( ) { string sInput ; getline ( cin , sInput , '\n' ) ; int Time = 1 ; int Count = 0 ; vector < string > Storage ; for ( int i = 0 ; i < sInput . size ( ) ; i + + ) { for ( int j = 0 ; ( j + Time - 1 ) < sInput . size ( ) ; j + + ) Storage . push_back ( sInput . substr ( j , Time ) ) ; Time + + ; } bool * Visited = new bool [ Storage . size ( ) * sizeof ( bool ) ] ; for ( int i = 0 ; i < Storage . size ( ) ; i + + ) { Visited [ i ] = true ; for ( int j = 0 ; j < Storage . size ( ) ; j + + ) { if ( i ! = j & & Storage [ i ] = = Storage [ j ] ) { Visited [ i ] = false ; Visited [ j ] = true ; break ; } } } for ( int i = 0 ; i < Storage . size ( ) ; i + + ) if ( Visited [ i ] ) Count ...
댓글 쓰기
자세한 내용 보기