[백준] 9735번 삼차 방정식 풀기 문제풀이

https://www.acmicpc.net/problem/9735

9735번: 삼차 방정식 풀기

문제

삼차 방정식 Ax3 + Bx2 + Cx + D = 0 의 모든 실수 해를 찾는 프로그램을 작성하시오.

입력으로 주어지는 방정식은 정수 해를 적어도 한 개 갖는다.

A, B, C, D는 -2,000,000보다 크거나 같고, 2,000,000보다 작거나 같은 정수이고, A는 0이 아니다. 모든 해는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같다. 주어지는 방정식의 해의 차이는 10-4보다 크다.

 

아이디어

반드시 정수 해를 하나도 가진다는 점을 잘 이용해야 한다고 생각했습니다.

조립제법을 통해 해를 얻을 때 그 해는 반드시 상수항의 약수 혹은 0에 해당할 것이므로 첫 번째 해를 구할 수 있습니다.

이를 통해 삼차 방정식을 이차 방정식으로 줄일 수 있습니다.

이차 방정식의 판별식을 이용해 그 이차방정식이 몇 개의 해를 가지는지 판단하고 set에 넣고 출력하여 문제를 풀 수 있습니다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, A, B, C, D, a, b, c;
double X1, X2, X3;

int main()
{
    cin >> n;
    while(n--)
    {
        set<double>all_x;
        cin>>A>>B>>C>>D;
        int check=0;
        for(ll i=1;i<=abs(D);i++) //정수해가 반드시 존재하므로 D의 약수 혹은 0
        {
            if(D%i==0)
            {
                if(A*i*i*i+B*i*i+C*i+D==0)
                {
                    X1 = (double)i;
                    check++;
                }
                else if(-A*i*i*i+B*i*i-C*i+D==0)
                {
                    X1= -(double)i;
                    check++;
                }
            }
        }
        if(check==0) X1=0;

        a=A;
        b=A*X1+B;
        c=A*X1*X1+B*X1+C; //조립제법

        double ken=b*b-4*a*c; //판별식

        if(ken<0) //판별식<0이라면 이차방정식의 실수해가 존재하지 않음
        {
            printf("%f\n", X1);
        }
        else if(ken==0)// 판별식=0이라면 중근
        {
            X2=(double)(-b)/(double)(2.0*a);
            all_x.insert(X1);
            all_x.insert(X2);
            if(X1==X2)
            {
                printf("%f\n",X1);
            }
            else
            {
                for(auto x : all_x) printf("%f ", x);
                printf("\n");
            }
        }
        else// 판별식>0이라면 서로 다른 두 실수 해
        {
            X2=(double)((-(double)b+sqrt(b*b-4.0*a*c))/(2.0*a));
            X3=(double)((-(double)b-sqrt(b*b-4.0*a*c))/(2.0*a));
            all_x.insert(X1);
            all_x.insert(X2);
            all_x.insert(X3);
            for(auto x : all_x) printf("%f ", x);
            printf("\n");
        }
    }
    return 0;
}