백준 #1229 빅뱅의 여섯번째 멤버

이 문제는 수학적 법칙을 좀 생각해보면 더 빨리 풀 수 있을 것 같은데, 일단 복잡해서 패스를 했습니다.   Gold IV 난이도이지만, 단순 무식한 방법으로 프로그램을 짰네요.

 

Big Bang!?

다각수라는 것은 도형을 확장하면서 생기는 점들의 수입니다.  3각수는 잘 알려져 있고, 이 값은 1부터 n까지의 합과 동일합니다.  여기서는 6각수가 나오는데, 6각수는 \(n(2n-1)\) 의 수식으로 표현되며, 1, 6, 15, 28, ... 형태로 늘어나는 수입니다.

 

이 6각수를 적절하게 더해서 모든 수를 표현할 수 있습니다.  6각수의 첫번째 수가 1이므로, 최악의 경우에는 1을 여러번 더할 수가 있습니다.  어떤 수가 주어졌을 때, 6각수를 몇개 가지고 표현할 수 있는지 알아보라는 것이 문제입니다.

 

수학적으로 분석을 할 필요가 있겠지만,  전, 6각수를 일일이 다 구한 다음에 무식하게 경우로 나누어서 풀었습니다.  시간이 많이 걸리겠지만, 그 부분은 150개정도를 미리 연산한 데이터로 커버를 했습니다.  그리고 이미 알려진 바와 같이 130이 5개 이상의 6각수를 필요로 하는 마지막 수라는 것을 알기 때문에, 경우의 수를 줄이는데 사용했습니다.  146858이 4개 이상의 6각수를 필요로 하는 마지막 수라는 것까지 활용하기에는 좀 무리가 있었네요.

 

제가 짠 소스입니다.  참고용으로 봐주세요.

//------------------------------------------------------------------------------
//  baekjoon #1229 - Sixth member
//    - by Aubrey Choi
//    - created at 2020-01-08
//------------------------------------------------------------------------------
#include <stdio.h>
#include <algorithm>

int hex[708], dp[150]={0,1,2,3,4,5,1,2,3,4,5,6,2,3,4,1,2,3,3,4,5,2,3,4,4,5,6,3,1,
2,2,3,4,4,2,3,3,4,5,5,3,4,4,2,3,1,2,3,4,3,4,2,3,4,5,4,2,3,3,4,2,3,3,4,4,5,1,2,3,
4,5,3,2,2,3,3,4,4,3,3,4,2,3,4,3,4,4,3,3,4,2,1,2,3,2,3,3,2,3,4,3,3,4,3,4,3,2,3,4,
3,4,2,3,4,5,4,4,3,3,2,1,2,3,4,4,3,2,3,4,4,5,4,2,3,3,2,2,3,3,3,4,3,3,4,4,4,4,3,2,3};
int dfs(int n, int k=0, int m=708)
{
  if(n<150) return k+dp[n];
  int min=6, r;
  int i=(std::lower_bound(hex,hex+m,n+1)-hex)-1;
  if(hex[i]==n) return k+1;
  for(;i>0&&hex[i]*(4-k)>=n;i--)
  {
    r=dfs(n-hex[i],k+1,i+1);
    min=(r<min)?r:min;
  }
  return min;
}
int main()
{
  int n, i;
  scanf("%d",&n);
  for(i=0;i<708;i++) hex[i]=i*(2*i-1);
  printf("%d\n", dfs(n));
}