백준 BOJ 9735 - 삼차 방정식 풀기

어제 제법 고민했는데 안풀렸던 문제

set같은거 썼으면 좀 빨리 풀었을지도?

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

9735번: 삼차 방정식 풀기

접근은 쉬운 편이다.

정수해가 반드시 하나 주어지므로

-2,000,000 부터 2,000,000까지 대입해가면서 정수해를 하나 찾으면 된다.

여기서 주의할점은 C++은 오버플로우가 일어날 수 있다는 것.

나는 파이썬으로(PyPy3) 해결했다.

이렇게해서 정수해를 N이라 하면

(x-N)(ax^2.....) 같은 꼴로 조립제법을 적용시켜줄수 있다

이러면 x-N이라는 일차식과 이차식 하나가 나오게 되는데

이 이차식에 대한 근을 구해주면 된다.

 

근의공식을 사용하기 전에, b*b - 4*a*c (판별식)을 사용해서

허근이 생기는 경우, 중근이 생기는 경우를 판별을 해주어야만 한다.

중근이 생기는 경우에는 삼중근인지도 판별해주고

일반적인 실근 두개가 생기는 경우도

중근이 있는지 반드시 검사해보아야만 한다.

 

실수 연산오차를 줄이기 위해 파이썬의 Decimal을 사용해주었다.

10진법 기반 실수라 연산오차가 적다고 한다.

 

그러면 깔끔하게 AC를 받을 수 있다.

---

재채점으로 탈탈 털려서 C로 다시짰다

9735번은 그렇게 빡빡하지 않아서 long double 자료형을 사용해주면 해결가능하다.

그리고 위에서 말한 set도 적용시켜보았다.

 

소스코드는 수정된 버전이다

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
set<ld> s;

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	
	int N;
	cin >> N;
	
	while(N--){
		s.clear();
		ld A,B,C,D;
		cin >> A >> B >> C >> D;
	
		for(ld i=-2e6; i<=2e6; i+=1){
			if(A*i*i*i + B*i*i + C*i + D == 0){
				s.insert(i);
				break;
			}
		}
		
		B += A*(*s.begin());
		C += B*(*s.begin());
		
		ld inner = B*B-4*A*C;
		//cout << "{" << inner << "}";
		if(inner >= 0){
			s.insert((-B+sqrt(inner))/(2*A));
			s.insert((-B-sqrt(inner))/(2*A));
		}
	
	
		for(auto it = s.begin(); it!=s.end(); it++){
			cout << *it << " ";
		}
		cout << "\n";
	}
	return 0;
}

(통곡의 솔브시도)