[백준 538번] 제곱근 작도 풀이

 

5389번: 제곱근 작도

 

 

H에서 y 사이의 거리를 r, H에서 x 사이의 거리를 l, x와 y 사이의 거리를 루트 n 이라 할 때, 세 변은 직각삼각형을 이루고 있으므로 다음을 만족한다.

 

$$ (\sqrt{n})^2 + l^2 = r^2$$

 

문제에서는 n 값을 알려주고 있으므로, 위의 식을 만족시키는 l과 r의 값 중 가장 작은 값들을 구하면 된다.  수식을 변형해보면, 

 

$$(\sqrt{n})^2+l^2 = r^2 (r > l)$$

$$ (\sqrt{n})^2 = r^2 - l^2$$

$$n = (r + l)*(r - l)$$

 

r + l 과 r - l 은 n 의 약수이다. 즉, n 이 약수 a와 b의 곱이 될 때 r + l = a, r - l = b 가 되는 r과 l의 조합이 있는지 찾는다.

 

for (int i = 1; i*i <= n; i++) {

  if (n%i != 0) continue;
  int diff = i;
  int sum = n/i;
  if ((sum+diff)%2 != 0) continue;
  int r = (sum+diff)/2;
  int l = r-diff;
  v.push_back({l, r});
}

 

n의 약수를 구하기 위해 1부터 n까지의 자연수를 모두 탐색해도 된다. 하지만 n의 최댓값 10^9가 입력될 경우 시간초과가 발생할 것이다. n의 약수는 i=1 부터 i*i <= n 이 되는 i 들로 n을 나누어 탐색이 가능하다. (약수의 기본적 성질을 이용한 매우 유용한 풀이법이다.) 

 

n이 i로 나누어떨어진다면, i와 n/i 는 n의 약수이고 두 수의 곱은 n 이 된다. 두 수 중 작은 수 i 를 r과 l의 차(diff) 라 하고, 더 큰 수 n/i 를 r과 l 의 합(sum) 이라 한다.

 

$$ n = (r - l)*(r + l)$$

$$ n = i * n/i$$

$$ r - l = i(diff), r + l = n/i(sum)$$

 

따라서 r - l = i(diff) 이고, r + l  = n/i(sum)을 만족시키는 정수 r과 l이 존재하는지 확인한다.

 

$$ r = diff + l$$

$$ l = sum - r$$

$$\therefore r = (sum + diff) / 2$$

 

(sum + diff) 를 2로 나누었을 때 나누어 떨어지면 정수 r 값이 존재하므로 r 과 l 을 구해 저장하면 된다.

 

조건을 만족하는 r과 l의 조합이 여러개일 때 가장 작은 수를 출력하라고 했다. 따라서 r과 l을 값을 pair<int, int>로 저장한 벡터를 정렬하여 가장 처음에 있는 값을 출력한다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
using namespace std;
using ii = pair<int, int>;

int main() {

    int T;
    scanf("%d", &T);

    for (int t = 0; t < T; t++) {

        int n;
        scanf("%d", &n);

        vector<ii> v;
        for (int i = 1; i*i <= n; i++) {
            
            if (n%i != 0) continue;
            int diff = i;
            int sum = n/i;
            if ((sum+diff)%2 != 0) continue;
            int r = (sum+diff)/2;
            int l = r-diff;
            v.push_back({l, r});
        }

        sort(v.begin(), v.end());
        if (v.size() == 0) printf("IMPOSSIBLE\n");
        else printf("%d %d\n", v[0].first, v[0].second);
    }
    return 0;
}