기본 콘텐츠로 건너뛰기

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

댓글

댓글 쓰기

이 블로그의 인기 게시물

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

11478 : 서로 다른 부분 문자열의 개수 (미제) [C++]

# include < iostream > # include < vector > # include < string > using namespace std ; int main ( ) { string sInput ; getline ( cin , sInput , '\n' ) ; int Time = 1 ; int Count = 0 ; vector < string > Storage ; for ( int i = 0 ; i < sInput . size ( ) ; i + + ) { for ( int j = 0 ; ( j + Time - 1 ) < sInput . size ( ) ; j + + ) Storage . push_back ( sInput . substr ( j , Time ) ) ; Time + + ; } bool * Visited = new bool [ Storage . size ( ) * sizeof ( bool ) ] ; for ( int i = 0 ; i < Storage . size ( ) ; i + + ) { Visited [ i ] = true ; for ( int j = 0 ; j < Storage . size ( ) ; j + + ) { if ( i ! = j & & Storage [ i ] = = Storage [ j ] ) { Visited [ i ] = false ; Visited [ j ] = true ; break ; } } } for ( int i = 0 ; i < Storage . size ( ) ; i + + ) if ( Visited [ i ] ) Count ...
댓글 쓰기
자세한 내용 보기