기본 콘텐츠로 건너뛰기

2579 : Climbing stairs (Dynamic Programming) [C,C++]

This game has three rules as you know.

1. Stairs can be climbed one step at a time or two steps at a time. That is, by stepping on one stair, you can go up to the next stair, then the next stair.
2. You should not step on all three consecutive stairs. However, the starting point is not included in the stairs.
3. The last arriving stairs must be stepped on.

In other words,
rule 2, If you have climbed two stairs in succession, the next action must be a 'jump'.
rule 3, The maximum value is the value of the last step.

The most important thing to solve this problem is to store two values in one step because there is a 'jump' variable. 

Therefore, we must use a dynamic two-dimensional array.

You can get the maximum value by storing the values of 'jump' and successive steps.

<pseudo code>

*Source of the problem = https://www.acmicpc.net/problem/2579
*문제 출처 : BAEKJOON ONLINE JUDGE
라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

6359 : 만취한 상범 (Dynamic Programming) [C++]

# include < iostream > # include < vector > using namespace std ; int Num_of_Divisor ( int n ) { int Count = 0 ; for ( int i = 1 ; i < = n ; i + + ) if ( n % i = = 0 ) Count + + ; return Count ; } int main ( ) { int Testcase ; cin > > Testcase ; while ( Testcase - - ) { int Rooms ; cin > > Rooms ; vector < int > Prisons ; for ( int i = 0 ; i < Rooms ; i + + ) Prisons . push_back ( 0 ) ; for ( int i = 1 ; i < Prisons . size ( ) + 1 ; i + + ) { if ( ( Num_of_Divisor ( i ) % 2 ) = = 0 ) Prisons [ i - 1 ] = 0 ; else Prisons [ i - 1 ] = 1 ; } int Fleer = 0 ; for ( int i = 0 ; i < Prisons . size ( ) ; i + + ) if ( Prisons ...
댓글 쓰기
자세한 내용 보기

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
댓글 쓰기
자세한 내용 보기