수학(2)
-
백준 14256번, SSR 풀이
문제 백준 14256번 풀이 $ SSR(A, B) = (\sqrt{A} + \sqrt{B}) ^ 2 $이 정수가 되어야 합니다. 식 정리를 해봅시다. $$ = A + B + 2 \cdot \sqrt{AB} $$ $A, B$는 이미 정수이므로, $ \sqrt{AB} $가 정수가 되면 됩니다. 따라서, $ AB $가 제곱수가 되면 됩니다. 이제, $ AB $가 제곱수가 되는 경우의 수를 모두 구하면 됩니다. $ A $를 고정시키고, 가능한 $ B $의 개수를 세봅시다. $ A $를 소인수 분해한 뒤, 지수가 홀수인 밑만 곱해준 수를 $ c $라고 정의합니다. 그러면, $ B $는 $ c \cdot k ^ 2 $이라고 둘 수 있습니다. ($k$는 임의의 정수) (왜냐하면, $B$가 항상 $c$의 배수여야 $ ..
2021.02.19 -
백준 2737번, 연속 합 풀이
문제 백준 2737번 풀이 $n$을 $a$부터 $b$까지의 합으로 나타내면 아래와 같습니다. $$ n = a + a + 1 +\ \cdot\cdot\cdot \ + b - 1 + b $$ $a$부터 $b$까지 $k$개를 뽑는다고 하면 첫째항이 $a$이고 끝항이 $a + k - 1$가 되며, 등차가 1입니다. 등차수열의 합 공식에 의해서 $$ n = \frac{k(2a + k - 1)}{2} $$ 로 나타낼 수 있습니다. 식을 정리하면 $$ k^2 + k(2a - 1) - 2n = 0 $$ 으로 나타낼 수 있고, 근의 공식에 의해서 $$ k = \frac{1 - 2a \pm \sqrt{4a^2 - 4a + 1 + 8n}}{2} $$ 이 됩니다. 뽑는 수 $k$를 최대로 하려면, 첫째항 $a$를 $ 1$로 ..
2021.01.27