#77 소수들의 합(Dynamic Programming, Back tracking)

이번 문제는 난이도 25%로 설정되어 있지만, 워낙 작은 숫자들로 이루어져 있기 때문에 어렵지 않게 풀 수 있습니다.

 

10을 소수들의 합으로 표현한다면, 다음과 같이 총 5가지로 표현할 수 있습니다.  동일한 소수를 여러번 쓰는 것이 가능하고, 순서없는 조합으로 표현했을 때입니다.  아래와 같이 큰 소수부터 차례대로 나열할 수도 있고, 소수의 빈도만 따져도 됩니다.

 

Summation 10 of primes

이러한 경우의 수가 5,000이 넘는 가장 가장 작은 수를 찾으라는 것이 문제입니다.

 

사실 어떤 수가 주어졌을 때, 경우의 수를 따지는 것은 크게 어렵지 않습니다.  백트랙킹 방법을 이용해서 풀 수도 있고, 동적 프로그래밍을 이용해서 풀 수도 있습니다.  하지만 경우의 수가 특정수를 넘는 가장 작은 수를 찾는 것은 동적 프로그래밍으로는 조금 한계가 있습니다.

 

일단 백트래킹 방법입니다.  다음 함수는 주어진 수에 대해서 합이 되는 경우의 수를 반환해주는 자기 호출 함수입니다.  소수들 리스트는 미리 구해놓습니다.

 

int GetCaseCount(int remain, int index)
{
  if( remain == 0 ) return 1;
  if( index < 0 ) return 0;

  int count = 0;
  
  for( int i = index ; i >= 0 ; i-- )
  {
    for( int j = 1 ; j*primes[i] <= remain ; j++ )
    {
      count += GetCaseCount(remain-j*primes[i], i-1);
    }
  }

  return count;
}

 

평범한 백트래킹 기법을 이용해서 원하는 합에 대한 인덱스를 출력하게 합니다.  사실 여기서 동적 프로그래밍을 이용할 수도 있습니다.  주어진 remain에 대한 출력값은 항상 동일할테니, 굳이 여러번 계산할 필요가 없겠죠.

 

이를 이용한 풀이 함수는 다음과 같이 작성했습니다.

 

void solve1()
{
  int pcount = 0;
  primes[pcount++] = 2;
  primes[pcount++] = 3;
  
  for( int p = 5 ; pcount < PCOUNT ; p+=2 )
  {
    bool isPrime = true;
    for( int i = 1; primes[i]*primes[i] <= p ; i++ )
      if( p%primes[i] == 0 ) { isPrime = false; break; }
    if( isPrime ) { primes[pcount++] = p; }
  }
  
  for( int c = 10 ;  ; c++ )
  {
    int first = pcount-1;
    while( primes[first] >= c ) first--;
    if( GetCaseCount(c, first) > N ) { printf("Ans = %d\n", c); break; }
  }
}

 

단순무식하게 10보다 큰 수에 대해서 경우의 수가 5,000이 넘게 되면 답을 출력하고 끝나도록 했습니다.

 

다음은 동적 프로그래밍을 이용한 방법입니다.  소수가 구해질때마다 동적 프로그래밍을 업데이트하고, 이전 소수부터 현재 소수까지 수 중에 경우의 수가 5,000이 넘는 수가 있는지 살펴봅니다.

 

void solve2()
{
  static int dp[1001]; int i, j, p, pp=2;
  for(i=0;i<=1000;i+=2) dp[i]=1;
  for(p=3;p<1000;pp=p,p+=2)
  {
    for(i=3;i*i<=p;i+=2) if(!(p%i)) break;
    if(i*i<=p) continue;
    for(i=1000;i>=p;i--) for(j=i-p;j>=0;j-=p) dp[i]+=dp[j];
    for(i=pp+1;i<=p;i++) if(dp[i]>N) break;
    if(i<=p) break;
  }
  printf("Ans = %d\n",i);
}

 

dp를 1,000까지만으로 잡은 이유는 간단한 한계치를 정했습니다.  1,000까지 2로만 더할 경우 총 500번을 더하게 됩니다.  여기에 3을 추가하게 되면, 2를 3번 더한 것 대신 3을 2번 더해도 같은 수가 되므로, 대략 2와 3의 합으로만 경우의 수를 구한다면, 167가지 정도가 나옵니다.  2와 5로만 이루어진다면 100가지 정도가 되겠죠.  2, 3, 5의 조합으로 되면 경우의 수는 꽤 많아지게 됩니다.  

 

여하튼 첫번째 방법보다 속도는 빠르지만, 무리할 수 있는 추측을 한 셈이므로, 가장 바람직한 알고리즘은 첫번째 해결 방법에 소수를 필요할 때 더 구하고, 동적 프로그래밍을 적용하는 방법일 듯 합니다.