4개의 댓글이 있습니다.

• 
  pumpyboom

  #define _CRT_SECURE_NO_WARNINGS
  #include
  #include

  int cnt = 0;
  int findMaxTree(int ** ar, int size, int i, int j, int n1, int n2);
  void findWay(int ** ar, int size, int i, int j, int n1, int n2, int max);

  int main(void)
  {

  int testCase;
  int n;
  int ** ar;
  int max = 0;
  
  scanf("%d", &testCase);
  
  
  for (int i = 0; i < testCase; i++)
  {
  
      scanf("%d", &n);
  
      ar = (int**)malloc(sizeof(int*)*n);
  
      for (int i = 0; i < n; i++)
          ar[i] = (int*)malloc(sizeof(int)*(i + 1));
  
  
      for (int i = 0; i < n; i++)
      {
          for (int j = 0; j <= i; j++)
              scanf("%d", &ar[i][j]);
      }
  
  
      max = findMaxTree(ar, n, 0, 0, ar[0][0], ar[0][0]);
  
      findWay(ar, n, 0, 0, ar[0][0],ar[0][0],max);
  
      printf("%d", cnt);
  
      cnt = 0;
  }
  
  return 0;

  }

  void findWay(int ** ar, int size, int i, int j, int n1,int n2, int max)
  {

  if (i >= size - 1)
  {
      if (n1 == max)
          cnt++;
  
      return;
  }
  
  
  int x1 = n1;
  int x2 = n2;
  
  x1 += ar[i+1][j];
  x2 += ar[i + 1][j + 1];
  
  findWay(ar, size, i + 1, j, x1, x1, max);
  findWay(ar, size, i + 1, j + 1, x2, x2, max);
  
  
  return;

  }

  int findMaxTree(int ** ar, int size, int i, int j, int n1, int n2)
  {

  int x1 = n1;
  int x2 = n2;
  
  if (i >= size - 1)
  {
      if (x1 > x2)
          return x1;
      else
          return x2;
  }
  
  x1 += ar[i + 1][j];
  x2 += ar[i + 1][j + 1];
  
  int len1 = findMaxTree(ar, size, i + 1, j, x1, x1);
  int len2 = findMaxTree(ar, size, i + 1, j + 1, x2, x2);
  
  if (len1 >= len2)
  {  
      return len1;
  }
  else
  {
      return len2;
  }

  }

  
  9년 전 link

• 
  pumpyboom

  이것은 제가 짠 코드이긴한데... 코드에 대한 문제보다는...
  시간초과를 해결하는 생각을 좀 더 듣고싶습니다

  
  9년 전 link

• 
  fleo0917

  중복계산을 없에야 합니다. 예를들어 3층짜리 삼각형의 각 칸을 아래처럼 순서대로 번호를 메기고,
  0
  1 2
  3 4 5
  각 위치에서의 함수호출을 f(위치)로 나타내면 f(0)는 이렇게 전개될겁니다.
  f(0) -> f(1)+f(2) -> f(3)+f(4)+f(4)+f(5)
  보시면 아시겠지만 f(4)가 두 번 호출됩니다. 3층짜리 피라미드에서는 겨우 두 번이지만 20층만 되도 수만번의 중복 호출이 발생합니다. 이걸 한 번으로 줄일 수 있는 방법을 생각해보세요.
  내가 만든 함수는 위치 뿐만 아니라 다른 인자도 받고 있으니까 중복이 아닌데? 라고 생각하실 수도 있겠지만 그게 사실 꼭 그 자리에 있어야 하는 건 아닙니다. 다른 방법으로 나타내는 방법을 생각해보세요.
  이 문제는 TRIANGLEPATH문제의 확장판입니다. 이걸 먼저 풀어보는 게 도움이 될 겁니다.

  
  9년 전 link

• 
  pumpyboom

  감사합니다! 나중에 다시 댓글로 답변 하겠습니다

  
  9년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.