[파이썬] 백준 9735 삼차방정식

제가 풀땐 9퍼였는데 정답률 떡상중

처음에 문제를 보면 입력으로 주어지는 방정식은 정수 해를 적어도 한 개 갖는다고 나와 있다.

그렇다면 이 문제의 풀이로는 두 개를 생각할 수 있을 것 같다.

1. 극대극소를 찾아 구간을 나눈 후 최대 3개의 구간에 대하여 이분탐색을 진행하기

이런 함수가 주어졌다고 가정해보자

f = (x-1)(x-2)(x-3)

f'(x)를 구하여 극점들을 찾고 (-,극점1), (극점1,극점2), (극점2,+) 세 개의 구간에서 이분탐색을 진행하여

해들을 구해보려고 했지만 극댓값이나 극솟값의 좌표가 실수라면

근을 구할때 오차가 날 것 같아서 시도하지 못했다.

f'

2. 정수해로 인수분해를 하여 이차식으로 만든 후 근의공식으로 구하기

이 방법을 사용하려면 정수해를 구해서 인수분해를 해야 하는데

우리가 옛날부터 해를 찾을 때 많이 썼던 방법이 있다.

x = ±(D의 약수)/(A의 약수)

def HI(num):
    L = []
    for i in range(1,int(num**0.5)+1):
        if num%i == 0:
            L.append(i)
            if num//i != i:
                L.append(num//i)
    return L

def ARC(d,a):
    dlist = HI(d)
    alist = HI(a)
    for i in dlist:
        for j in alist:
            N = i//j
            if N == 0:
                continue #zero division 방지 
            for l in [N,-N]:
                judge = 0
                for k in sik: #sik = [A, B, C, D]
                    judge = (judge * l) + k #빠르게 다항식의 값 구하기
                if judge == 0:
                    return l 

이제 정수해를 받고 인수분해를 해야 한다.

인수분해는 조립제법으로 쉽게 할 수 있다.

우리가 구한 정수해 N으로 조립제법을 해본다면

2차항으로 변하고, 나머지는 AN^3+BN^2+CN+D가 나온다.

그러나 N은 삼차방정식의 해이므로 AN^3+BN^2+CN+D = 0이 성립하므로

Ax^2+(AN+B)x+AN^2+BN+C 만 남는다.

이제 이차식을 근의공식에 넣기 전에

a = A, b = (AN+B), c = AN^2+BN+C로

다시 예쁘게 정리를 한 후에

판별식에 넣어서 허근 중근 두근인지 판별을 하고

근이 있다면 미리 구한 근과 중복하는지 검사만 하고

제출하면 끗이다.

정답코드

import sys

r = sys.stdin.readline

def HI(num): #약수구하기
    L = []
    for i in range(1,int(num**0.5)+1):
        if num%i == 0:
            L.append(i)
            if num//i != i:
                L.append(num//i)
    return L

def ARC(d,a): #성질 이용해 정수해 빠르게 구하기
    dlist = HI(d)
    alist = HI(a)
    for i in dlist:
        for j in alist:
            N = i//j
            if N == 0: #zero division 방지
                continue
            for l in [N,-N]:
                judge = 0
                for k in sik: #sik = [A,B,C,D]
                    judge = (judge * l) + k #빠르게 다항식 합 구하기(안빠름)
                if judge == 0:
                    return l 

for _ in range(int(r())):
    sik = list(map(int, r().split()))
    if sik[3] == 0: #상수항이 없다면 0인 근이 적어도 하나 존재
        ans1 = 0
    else:
        ans1 = ARC(abs(sik[3]),abs(sik[0]))
    A = sik[0]
    B = A*ans1+sik[1]
    C = B*ans1+sik[2]
    D = B*B-4*A*C
    answer = []
    answer.append(ans1)
    if D == 0:
        ans2 = -(B/(2*A))
        if ans1 != ans2:
            answer.append(ans2)
    elif D > 0:
        ans2 = (-B+(D)**0.5)/(2*A)
        ans3 = (-B-(D)**0.5)/(2*A)
        if ans1 == ans2:
            answer.append(ans3)
        elif ans1 == ans3:
            answer.append(ans2)
        else:
            answer.append(ans2)
            answer.append(ans3)
    answer.sort()
    print(" ".join(map(str,answer)))

원래 처음에는 정수해를 구하는 곳을 -2백만 부터 +2백만까지 브루트포스로 구했었는데

귀찮음을 감수하고 고쳤더니

4000ms 에서 156ms까지 줄었다.

근데 역시 너무 귀찮은것 같다.