[백준] 17211. 좋은날 싫은날

17211번: 좋은 날 싫은 날

## 메모리 초과로 실패

## tree를 삭제하는 식으로 다시 작성해야 할 듯 하다.

 

IDEA

이진트리로 하루가 지날 때마다, 확률의 수가 2배로 늘어남에 따라 
전날 확률과 현재의 확률을 누적했다.

둘째 날 가능한 경우의 수가 2개이고
셋째 날 가능한 경우의 수는 2²개
n-1 째날 가능한 경우는 2ⁿ 개이다. 

 

int main(void)
{
  int n;
  int now;
  int idx = 0;
  double sum = 0;
  vector<double> p(4);
  vector<vector<double>> tree;

  cin >> n >> now;
  cin >> p[0] >> p[1] >> p[2] >> p[3];

  for(int i=0; i<n; i++)
  {
    vector<double> v;
    sum = 0;
    if(now == 0 && i==0) //첫날 좋은 날일 경우
    {
      v.push_back(p[0]);
      v.push_back(p[1]);
    }
    else if(now == 1 && i==0) //첫날 나쁜 날일 경우
    {
      v.push_back(p[2]);
      v.push_back(p[3]);
    }

    else //이후 날들
    {
      for(int k=0; k<pow(2, i+1); k++) // 이전 날의 확률을 참고해 곱한다.
      {
        v.push_back(tree[i-1][idx] * p[k%4]);

        if(k%2 == 1)
        {
          sum += tree[i-1][idx] * p[k%4];
          idx++;
        }

        
      }

    }
    idx = 0;
    
    tree.push_back(v);

  }

  cout << (1-sum) * 1000<< '\n' << sum * 1000;
  return 0;
}