* 문제풀이

  카드가 최대 50장으로 제한되어 있으므로 경우의 수가 얼마 없습니다 :D (실제로 계산해보진 않았지만..) 따라서 Brute-Force하게 일일이 해도 풀리는 문제이지요.

  일단 {3,1,3}과 {1,3,3}이 같은 상태이므로 (예제 참조) 결국에는 어떤 상태가 입력으로 주어질 때, 이를 소트해도 같은 상태라는 것을 알 수 있습니다. 이렇게 소트하는 이유는 중복체크를 보다 편하게 하기 위해서이지요.

  저는 중복체크를 map을 이용하여 해결하였습니다. 이런 류의 문제에서는, key값을 vector <int> 으로 하면 사용하기가 편하거든요. (물론 데이터가 크다면 속도...문제를 유의해야 합니다.)

#define all(x) (x).begin(),(x).end() map<vector<int>, int> mheap; struct SolitaireSimulation {    int periodLength(vector <int> heaps) {       sort(all(heaps));       mheap[heaps] = 0;       int now = 0;        while (true)       {          now++;           vector <int> nheap;          nheap.push_back(heaps.size());          for (int i = 0; i < heaps.size(); ++i)             if (heaps[i] > 1) nheap.push_back(heaps[i] - 1);          sort(all(nheap));          heaps = nheap;           if (mheap.count(heaps) > 0)             return now - mheap[heaps];           mheap[heaps] = now;       }       return -1;    } };

  * 문제풀이

  전형적인 Dynamic Programming 문제입니다. table[i][j]를 빨간카드가 i장, 검은카드가 j장 있을때의 최대 기대값이라고 정의합시다. 그러면 점화식은 아래와 같이 나오게 됩니다.

  table[i][j] = i / (i + j) * (1 + table[i - 1][j])    /// 빨간 카드가 나올 확률 * 빨간 카드가 나왔을 때의 기대값
                   + j / (i + j) * (table[i][j - 1] - 1)    /// 검은 카드가 나올 확률 * 검은 카드가 나왔을 때의 기대값

  단, table[i][j]는 최소 0이상이 됩니다. 만약 0보다 작게된다면 게임을 그만두는것이 최선의 방법이니까요.

  문제에서 약간 tricky[?]한 점은 array size입니다. 보통 이런 경우에는 2 * 5000 배열을 잡거나 5000짜리 1차원 배열을 두개 잡아서 shift하는 방식을 자주 사용합니다. 현재 상태의 값을 구하기 위해서는 바로 이전 상태의 값만 알아도 되거든요. 사실 1차원 배열 하나만 가지고도 이 문제를 풀 수 있긴 합니다 :D. 저는 2 x 5000 배열을 잡아서 상호참조하는 방법을 사용하였습니다.

double table[2][5001]; struct RedIsGood {    double getProfit(int R, int B) {        memset(table, 0, sizeof(table));       for (int i = 1; i <= R; ++i)       {          int a = i & 1, b = 1 - a;           table[a][0] = i;          for (int j = 1; j <= B; ++j)          {             table[a][j] = 0.0;             double p = (i * 1.0 / (i + j)) * (table[b][j] + 1) + (j * 1.0 / (i + j)) * (table[a][j - 1] - 1);             table[a][j] >?= p;          }       }        return table[R & 1][B];    } };

Let A=(a₁,...,a_N) and B=(b₁,...,b_N) be two different but equally large sets of coins, with a₁ >= a₂ >= ... >= a_N and b₁ >= b₂ >= ... >= b_N. Let x be the smallest index such that a_x != b_x. If a_x > b_x, we say that the set A is lexicographically larger than the set B.

  * 문제풀이

  우선 작은 문제에서부터 해결하도록 하지요. 수표의 범위가 100만 이하일 때를 풀어봅시다. (저는 대회때는 101만으로 잡았지만요.)

///  table[i] => i원짜리 수표를 기계에 넣었을 때, 리턴하는 최소 동전 수.        for (int i = 0; i <= 1010000; ++i) table[i] = i;       for (int i = 1; i < n; ++i)       {          for (int j = outputValues[i]; j <= 1010000; ++j)          {             table[j] <?= table[j - outputValues[i]] + 1;          }       }

 기본 상태는 1원짜리 동전만 return하는 것이기 때문에 table[i] = i로 세팅을 해 줍니다. 그 다음부터 outputValues[i]원짜리를 사용해서 더 적은 동전을 사용할 수 있는지 확인하여 갱신합니다. {참고로 a <?= b는 a = min(a, b)와 같은 연산입니다. } 또한 초기에 outputValues값에서 inputValue이상의 동전들을 배제하면, 올바른 답을 구할 수 있지요. (배제하지 않는다면 대참사가 발생합니다 ㅠㅠ 예제가 안나올꺼에요 :D)

  그러면 이제 이 테이블을 가지고 작은 inputValue에 대해 답을 역추적해보도록 하겠습니다. 예제데이터인 {1, 5, 10}, inputValue = 21을 가지고 설명하겠습니다.

  1) 1원짜리 동전이 있다면? 변환할 필요가 없습니다. 
  2) 5원짜리 동전이 있다면, 우리는 거스름돈으로 {1}만을 리턴한다는 사실을 알 수 있죠. 따라서 1번의 변환이 필요합니다.
  3) 10원짜리 동전이 있을 때, {1, 5}의 거스름돈을 사용합니다. table[9]와 table[5] 중 작은쪽을 택하게 되겠지요. 만약 두 값이 같다면, 우리는 lexicographically larger 조건에 의해 5의 동전을 사용하고, table[5]를 참조하게 됩니다. 10원짜리 동전을 바꾸면 {5개, 1개}로 변환이 될 것이고, 1원짜리는 0번, 5원짜리는 1번 변환해야 하므로 총 2번의 변환이 필요하게 됩니다. { 10원->5원x1+1원x5 -> 1원x10 }
  4) 21원짜리 수표가 있을 때, {1, 5, 10}의 거스름돈을 사용할 수 있습니다. 위에서와 같이 table[20], table[16], table[11]을 볼 수 있습니다. 셋을 비교했을 때 제일 좋은 경우는 table[11]이 되고, 이를 반복하면 21원짜리 수표를 넣었을 때 {1개, 0개, 2개}를 리턴합니다. 21원짜리 수표를 넣으면 5번의 변환이 필요하게 되겠네요.

  일단 inputValue가 작은때는 위의 step으로 진행합니다. 말은 길게 썼지만 결론만 간단히 말하면, bottom-up 방식이랄까요.. 작은돈부터 차례대로 계산해 나가는 방식이죠.

  inputValue가 큰 경우에는 아래의 소스코드에서 사용했듯이 100만 이하가 될때(제 소스에선 100만5천이지만요) 까지는 제일 큰 동전을 변환한다고 두었습니다. 자세한 증명은 코드 밑에 첨부합니다. :$ 제가 이 값을 100만이라고 가정한 이유는, {1, 999, 1000}이고 997002의 데이터가 입력으로 주어진다면, 첫 턴에 999*998로 바꿔주는 것이 1000*997 + 1*2보다 적은 동전을 주기 때문이지요.

int table[1010001]; vector <vector <long long> > info; long long turn[55]; vector <long long> getSolution(long long v, vector<int> elem) {    vector <long long> ret(elem.size(), 0);    if (v > 1010000)    {       long long t = (v - 1005000) / elem.back();       ret[elem.size() - 1] = t;       v -= t * elem.back();    }     while (v)    {       int remain = 9999999;       int p = -1;       for (int i = 0; i < elem.size(); ++i)       {          if (v >= elem[i] && remain >= table[v - elem[i]])          {             remain = table[v - elem[i]];             p = i;          }       }       ret[p]++;       v -= elem[p];    }    return ret; } struct ChangeOMatic {    long long howManyRounds(vector <int> _outputValues, long long inputValue) {        // 필요없는 원소들은 지운다.       vector <int> outputValues;        for (int i = 0; i < _outputValues.size(); ++i)       {          if (_outputValues[i] < inputValue)             outputValues.push_back(_outputValues[i]);       }        int n = outputValues.size();       info.assign(n, vector <long long> (n, 0));        for (int i = 0; i <= 1010000; ++i) table[i] = i;       for (int i = 1; i < n; ++i)       {          for (int j = outputValues[i]; j <= 1010000; ++j)          {             table[j] <?= table[j - outputValues[i]] + 1;          }       }        vector <long long> elem;        info[0][0] = 1; turn[0] = 0;       for (int i = 1; i < n; ++i)       {          elem.pb(outputValues[i - 1]);          info[i] = getSolution(outputValues[i], elem);          turn[i] = 1;          for (int j = 0; j < info.size(); ++j)          {             turn[i] += info[i][j] * turn[j];          }       }        elem.pb(outputValues.back());        vector <long long> ret = getSolution(inputValue, elem);        long long rr = 1;       for (int j = 0; j < ret.size(); ++j)          rr += ret[j] * turn[j];        return rr;    } };
 

[  Hard - 왜 100만까지는 제일 큰 동전을 사용하면 되는지 증명하기 ]

  Let M = outputValues.back()  // 제일 큰 동전 이라고 정의하면
  A[i][j] : i * M + j 원을 i+1개의 동전만을 사용하여 만들 수 있는가? 로 정의할 수 있습니다. ( 0 <= j < M )

  그리고 위의 A는 2차원이므로, 이를 1차원으로 변환한 Set S[i]를 정의합니다. S[i] : { A[i][j] = TRUE를 만족하는 모든 j 의 set }

  집합 S를 잘 살펴보면, S[0] = outputValues 라는 것을 알 수 있습니다. 또한 S[0] ⊆ S[1] ⊆ S[2] ⊆ S[3] ... 이라는 것도 찾을 수 있지요. S[i - 1] ⊆ S[i] 가 되는 이유는, (i-1) * M + j원을 i개의 동전으로 만들었다면, 여기에서 M원짜리 동전을 사용하면 i*M+j원을 (i+1)개의 동전으로 만들 수 있기 때문입니다.

  즉 | S[0] | = outputValues.size() 가 되고, | S[0] | ≤ | S[1] | ≤| S[2] | 이며, | S[x] | 의 최대값은 M이기 때문에, 결국에는 x <= M 이전에 수렴한다는 사실을 알 수 있습니다. S[x]에서 수렴했다는 말은, "S[x+1] -> S[x]로 가기 위해서는 M원짜리 동전을 사용하면 된다." 를 의미합니다. 즉 100만 이상의 경우에는 항상 M을 사용해도 최적해가 나온다는 뜻이 됩니다.