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(Sum[i - 1] + i);

 int Count = 1;

 for (int i = 0; i < (Sum[100] + 101); i++)
 {
  if (Count != 101)
  {
   if (i == Sum[Count])
    Count++;
  }
  vector<int> Temp;
  Temp.resize(Count);
  this->Answer.push_back(Temp);
 }
}

void Combination::Increase(int t)
{
 for (int i = 0; i < this->Answer[t].size(); i++)
 {
  while(this->Answer[t][i] > 9)
  {
   this->Answer[t][i + 1]++;
   this->Answer[t][i] -= 10;
  }
 }
}

void Combination::GetSum(int t,int a, int b)
{
 for (int i = 0; i < Answer[a].size(); i++)
  Answer[t][i] = Answer[a][i] + Answer[b][i];
}

void Combination::GetAnswer(int n, int m)
{
 int Count = 1;
 for (int i = 1; i <= Sum[n]+m; i++)
 {
  if (i == Sum[Count] - 1)
  {
   Answer[i][0] = 1;
   continue;
  }
  else if (i == Sum[Count])
  {
   Count++;
   Answer[i][0] = 1;
   continue;
  }
  else
  {
   GetSum(i,i - Answer[i].size(), i - Answer[i].size() + 1);
   this->Increase(i);
  }
 }
 bool Flag = false;

 for (int i = this->Answer[Sum[n] + m].size() - 1; i >= 0; i--)
 {
  if (Answer[Sum[n]+m][i] != 0)
   Flag = true;
  if (Flag)
   cout << this->Answer[Sum[n]+m][i];
 }
}

<소스 코드>

*Source of the problem = https://www.acmicpc.net/problem/2407

*문제 출처 : BAEKJOON ONLINE JUDGE