기본 콘텐츠로 건너뛰기

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

댓글

댓글 쓰기

이 블로그의 인기 게시물

1094 : 막대기 [C++]

# include < iostream > # include < vector > using namespace std ; int main ( ) { vector < int > Stick ; Stick . push_back ( 64 ) ; int Target ; cin > > Target ; int Last = 0 ; while ( true ) { if ( Target = = 64 ) break ; int Sum = 0 ; for ( int i = 0 ; i < Stick . size ( ) ; i + + ) Sum + = Stick [ i ] ; if ( Target = = Sum ) break ; else if ( Target < Sum ) { Stick [ Last ] / = 2 ; Sum = 0 ; for ( int i = 0 ; i < Stick . size ( ) ; i + + ) Sum + = Stick [ i ] ; if ( Target < = Sum ) continue ; else Stick . push_back ( Stick [ Last + + ] ) ; } } cout < < Stick . size ( ) ; ...
댓글 쓰기
자세한 내용 보기

2407 : 조합 (Dynamic Programming) [C++]

어려웠다. 문제를 풀면서 솔직히 이게 되려나?? 메모리 제한걸리려는게 아닌가 싶었는데 만들면서 최대한 메모리를 작게 만들었더니 맞았습니다! 주어진 입력 값은 최대 100인데, 입력값을 입력하면 오버플로우가 나므로 자릿수 배열을 만들어주어야 한다! 처음으로 한 생각은 재귀! (n == m || m == 0) 참이면 1 거짓이면 [n-1], [n]번째에 계속 접근하기 결과는 20이 넘어가면 엄청난 시간이 걸림. 두 번째 한 생각은 3차원 배열이었다. 2차원 배열에 또 배열을 만들어 자릿 수를 다 저장하려 했으나~ for문이 3개나 들어가서 시간이 엄청 오래걸렸음. 결국 2차원 배열이지만 3차원의 효과를 내게끔 선언하였다. 2차원배열이 원래이런 식이라면 1 11 121 1331 14641 내가 만든 배열은 111121133114641 즉 한 차원을 줄일 수 있었고, 각 원소에 대한 파스칼의 삼각형을 이용한 덧셈 공식은  그 줄의 자릿수 사이즈를 이용하여 전에 있는 줄에 접근하였다. DP 사용!! Answer[i] = Answer[i-Answer[i].size()] + Answer[i-Answer[i].size()+1] 그리고 저장한 자릿수들을 거꾸로 출력해주면 그것이 정답! Combination() : 각 줄의 번호만큼 자릿수를 가지는 벡터 생성, 계속 쓰는 Sum 벡터 생성 Increase() : 각 자릿수가 10이 넘어가면 올림을 해준다. GetSum() : 각 자릿수를 더해준다. GetAnswer() : DP, 올림, 출력  Combination :: Combination ( ) { this - > Sum . push_back ( 0 ) ; for ( int i = 1 ; i < = 101 ; i + + ) Sum . push_back ( S...
댓글 쓰기
자세한 내용 보기

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