기본 콘텐츠로 건너뛰기

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

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

차이점이 두 가지가 있는데

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

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

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

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



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

댓글

댓글 쓰기

이 블로그의 인기 게시물

11401 : 이항계수 3 (Dynamic Programming, Divide and Conquer) [C++]

1번, 2번 문제들과 확연히 차이나는 입력의 범위. 400만 ! DP를 사용해서 풀 수 없는 문제이다 . 하지만 DP가 쓰이긴 한다! 수학은 너무 어렵다. 곱셈의 역원을 공부해보다가 모르겠어서 도움을 구했다. 왜 곱셈의 역원을 구해야하는가? N! / (K! * (N-K)!) 에서 K! * (N-K)! 의 역원을 구해야 하기 때문! 곱셈의 역원을 구하는 정리인 페르마의 소정리를 이용하면 p가 1000000007 이지만 분할 정복을 이용한 제곱 수 계산 덕분에 logP 시간 소요. 분할 정복을 이용한 제곱 수 계산은 계속 써먹을 것 같아서 따로 올려놓았다. DP가 쓰이는 부분은 구해준 400만의 역원을 바탕으로 모든 역원을 구하는 부분이다. 그러므로 총 시간 소요는 O(N+LogP) long long BinomialCoefficient :: GetNum ( int N , int K ) { this - > Factorial [ 1 ] = 1 ; for ( int i = 2 ; i < = 4000000 ; i + + ) this - > Factorial [ i ] = ( this - > Factorial [ i - 1 ] * i ) % P ; this - > Invert [ 4000000 ] = this - > Pow_DC ( this - > Factorial [ 4000000 ] , P - 2 ) ; for ( int i = 4000000 - 1 ; i > 0 ; i - - ) this - > Invert [ i ] = ( this - > Invert [ i + 1 ] * ( i + 1 ) ) % P ; if ( N = = K | | K = ...
댓글 쓰기
자세한 내용 보기

1978 : 소수 찾기 [C++]

# include < iostream > # include < vector > using namespace std ; int main ( ) { cin . tie ( NULL ) ; vector < int > Primes ; Primes . push_back ( 2 ) ; Primes . push_back ( 3 ) ; for ( int i = 4 ; i < 1000 ; i + + ) { bool IsPrime = true ; if ( i % 2 = = 0 | | i % 3 = = 0 ) continue ; for ( int j = 4 ; j < i ; j + + ) { if ( i % j = = 0 ) { IsPrime = false ; break ; } } if ( IsPrime ) Primes . push_back ( i ) ; } int N , Count = 0 ; cin > > N ; for ( int i = 0 ; i < N ; i + + ) { int Input ; cin > > Input ; for ( int j = 0 ; j < Primes . size ( ) ; j + + ) if ( Input = = Primes [ j ] ) Count + + ; } cout < < Count < < " \n " ; return 0 ; }
댓글 쓰기
자세한 내용 보기