백준 28237번 문제 풀이 - 수학 선생님의 고민(Easy)

문제 분석

주어진 이차식은 다음과 같다. $nx^2 + (n+1)x - (n+2)$

이를 정수 범위 내에서 인수분해 가능한지 판별하고, 가능하면 인수분해의 형태를 출력하는 문제이다.

풀이 방법

이 문제는 이차식을 정수 범위 내에서 인수분해하기 위한 정수 계수의 조합을 찾는 것이 핵심이다.

일반적인 형태의 인수분해는 다음과 같다. $(ax + b)(cx + d) = acx^2 + (ad + bc)x + bd$

즉, 이 문제에서는 아래의 방정식을 만족해야 한다.

• $ac=n$
• $ad+bc=n+1$
• $bd=−(n+2)$

알고리즘 설계

1. 모든 $a,c$의 조합을 찾는다. 이 때, $ac=n$ 이므로 $n$의 모든 약수 조합을 탐색한다.
2. 각각의 조합에 대해 $bd=−(n+2)$를 만족하는 $b,d$의 조합을 찾는다. 즉, $−(n+2)$의 모든 약수 조합을 탐색한다.
3. 위 조건을 만족하는 $a,b,c,d$가 발견되면, 해당 값을 출력하고 종료한다.
4. 모든 경우를 탐색했으나 조건을 만족하는 조합이 없다면, $-1$을 출력한다.

파이썬 구현 예시

def factorize(n):
    for a in range(1, int(n ** 0.5) + 1):
        if n % a == 0:
            c = n // a
            for b in range(-n-2, n+3):
                if b == 0 or (-(n+2)) % b != 0:
                    continue
                d = -(n+2) // b
                if a*d + b*c == n + 1:
                    return a, b, c, d
                if c*d + a*b == n + 1:
                    return c, b, a, d
    return -1

n = int(input())
res = factorize(n)
if res == -1:
    print(-1)
else:
    print(*res)

복잡도 분석

• 약수 조합 탐색에 걸리는 시간 복잡도는 $O(n)$이고, 내부의 추가 반복이 있지만 범위가 크지 않아 매우 효율적으로 작동한다.
• 제한 조건 $1≤n≤5000$ 내에서 충분히 빠르게 동작한다.