기본 콘텐츠로 건너뛰기

2239 : 동전 1 (Dynamic Programming) [C,C++]

예제의 입출력을 바탕으로 각 경우의 수를 배열에 저장하여 하나하나 서로의 관계를 찾아보았다.

1원으로 만들 수 있는 수들을 경우의 수 배열에 담고
2원으로 만들 수 있는 수들을 경우의 수 배열에 담고
5원으로 만들 수 있는 수들을 경우의 수 배열에 담는
그런 간단한 문제였다. 

예를 들어 6원은

111111, 11112, 1122, 222, 15 이렇게 5가지가 나오는 데
1원이 무조건 한개가 포함되어야 하는 숫자는 1원 + 5원 (4개)
2원이 무조건 한개가 포함되어야 하는 숫자는 2원 + 4원 (3개)
5원이 무조건 한개가 포함되어야 하는 숫자는 5원 + 1원 (1개)

그렇다면 Case[6] = (1)Case[5] + (2)Case[4] + (5)Case[1]이 된다.

여기서 주의해야 할 점은 중복을 발생시키지 말아야 한다는 것이다.

난 중복을 생각하지 못하여 식을 찾는 데에 시간이 오래 걸렸다.

중복을 발생시키지 않으려면!

동전 하나의 모든 경우의 수를 배열에 담고 다음 동전으로 넘어가야 한다.

동전과 경우의 수를 담는 배열을 사용하므로 당연히 2중 반복문을 사용하게 될 것이고
동전의 인덱스를 바깥 반복문에 위치시키면 되겠다.

int CoinClass::GetCase()
{
 for (int i = 0; i < this->Kind; i++)
 {  
  for (int j = 0; j <= this->Total; j++)
  {
   if (this->Coin[i] <= j)
    this->Case[j] += this->Case[j - this->Coin[i]];
  }
 }
 return Case[this->Total];
}
<pseudo code>

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