기본 콘텐츠로 건너뛰기

2156 : 포도주 시식(미제) (Dynamic Programming) [C,C++]

계단 오르기와 유사한 문제이다.

차이점이 두 가지가 있는데

하나는 계단 오르기 문제는 두개를 밟고 나면 다음 계단을 뛰어넘고 그 다음 계단을 무조건 밟아야 한다는 점이었다. 
포도주 시식 문제도 두개를 먹고 나면 다음 포도주는 뛰어 넘어야하지만 포도주 시식 문제는 여러 개를 뛰어넘어도 된다.

다른 하나는 계단오르기 문제는 마지막 계단이 최댓값이지만 포도주 시식 문제는 그렇지 않다.

5시간동안 풀어봤는데 계단오르기 문제와 유사하다는 생각이 박혀있어서 그런지
규칙을 못 찾겠다. 

내일까지 더 풀어보고 글을 업데이트해야겠다.



*Source of the problem = https://www.acmicpc.net/problem/2156
*문제 출처 : 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
댓글 쓰기
자세한 내용 보기