gee308   11달 전

문제를 기억해서 적어보면


n개 이하의 1*1*1 블럭을 이용하여 대각선의 길이가 정수인 직육면체의 갯수를 구하여라


예를들어 2*2*1 의 경우는 대각선의 길이가 3이므로 정수입니다

small까지는 그냥 a2 b2 c2 다 때려박아서 정수이면 출력시켜서 풀었는데

large는 도저히 천만이라는 숫자를 어떻게 구해야하는지 모르겠습니다

대회가 끝난후로도 계속 규칙 같은걸 생각해봤는데 모르겠습니다 ㅜ

혹시 방법 아시는분 계신가요???

game2k   11달 전

저는

sqrt(a^2 + b^2 + c^ 2) 는 정수

a*b*c <= 10000000 라는 조건을 이용해서 해결하였습니다

gee308   11달 전

그렇게 하면 large는 해결이 안되던데...


라지도 해결이 됐나요??

game2k   11달 전

5~10초 정도 걸리긴 했지만 라지도 풀렸어요

gee308   11달 전

정수 확인은 어떻게 하셨나요??


저는  int에다가 넣어서 같은지 비교했는데...

game2k   11달 전

문제에서 a*b*c를 계산해야 되기 때문에 1*1*1 부터 1000만*1000만*1000만중 모든 가능한 경우를 생각했습니다.

이때 1*1*2 와 1*2*1은 같기 때문에 중복되는 계산 제거를 위해 다음과 같이 for문을 구성했습니다.

#define MAX 10000000

for (long long a = 1; a <= MAX; ++a)
  for (long long b = a; b <= MAX; ++b)
    for (long long c = b; c <= MAX; ++c) {

//code  }

그리고 a*b*c 가 1000만 보다 작아야 되기 때문에 if문으로 적절히 break하였습니다.

for (long long a = 1; a <= MAX; ++a) {
    if (a * a * a > MAX)
        break;
        for (long long b = a; b <= MAX; ++b)  {
             if (a*b*b > MAX)
                 break;
             for (long long c = b; c <= MAX; ++c)   {
                 if (a*b*c > MAX)
                    break;
                 else {  //정수인지 확인 } 
             }
       }
}

비교는  if( sqrt(num) == (int)sqrt(num) ) 로 하였습니다.

계산된 결과에 대해 1000만개짜리 배열에 잡아서 정수이면 값을 1씩 증가시켜 전처리 해두었습니다.

전처리에 5~10초 정도 걸리고 답은 그냥 입력 보다 작은 갯수 더하면 돼서 금방 답이 나왔습니다. 시간제한이 5분이라.. 그냥 이렇게 제출했었네요. 다른 더 좋은 방법이 있는지는 모르겠습니다 ㅠㅠ

gee308   11달 전


      for (int i = 1; i < pow(a, 1.0 / 3.0); i++)
      {
         for (int j = i; j< sqrt(a); j++)
         {
            long long int ha = i*i + j*j;
            long long int hb = (j-1)*(j-1);
            int check =i*j;
            for (int k = j-1; k <= a; k++)
            {
               hb += 2*k + 1;
               check =check*k;
               if (check>a)
                  break;
               if (sqrt(hb+ ha) == (int)sqrt(hb+ ha))
               {
                  count++;
               }
            }
         }
      }


어디서 이런 시간차이가 생긴지 모르겠는데 정수판별부분을 이상하게 해서 그랬나봐요

다이나믹 프로그래밍 이렇게 사용할수도 있구나 알게되고 많은 도움 된거 같아요 감사합니다 ㅜㅜ

계산부분은 너무 안돼서 계속 최적화를 해봤어요 아마 이게 최선이라 저는 생각합니다...!!

a를 제일작은수 그다음b c를 제일 큰수라고 놓고 

한가지 궁금한건 문제 에서 n이 최대값이 천만이니까 미리 천만까지 구해놓고 계산하는 이 방식이 상관 없는건가요??


game2k   11달 전

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAX 10000000
int* table;
int main()
{
     int num_case, N;
     double num;
     table = new int[MAX+1];
     memset(table, 0, sizeof(int)*(MAX + 1));
     for (long long a = 1; a*a*a <= MAX; ++a)
     for (long long b = a; a*b*b <= MAX; ++b)
     for (long long c = b; a*b*c <= MAX; ++c){
        num = a*a + b*b + c*c;
        if (sqrt(num) == (int)sqrt(num))
             table[a*b*c]++;
     }
     for (int j = 1; j <= MAX; ++j)
          table[j] += table[j - 1];
     cin >> num_case;
     for (int i = 0; i < num_case; ++i) {
          cin >> N;
     printf("%d\n", table[N]);
     }
}

game2k   11달 전

네  위에 코드처럼 하면 그냥 미리 계산을 다 해놓아도 전혀 문제되지 않습니다.

요점은  매번 값을 찾기 위해 계산 하는것이 아니라 그러한 a, b, c 의 조합이 있었는가? 있었다면 몇개 있었는가? 하고 배열에서 찾아보는 것입니다.

댓글을 작성하려면 로그인해야 합니다.