[python] Baekjoon 백준 19532 : 수학은 비대면강의입니다 - 부르트포스

문제

백준 - 19532번
문제유형: 부르트포스

다음 연립방정식에서 $x$와 $y$의 값을 계산하시오.
$ax+by=c\\dx+ey=f$

입력조건

정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$)

문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $-999 \leq x,y \leq 999$ 의 정수인 경우만 입력으로 주어짐이 보장된다.

출력조건

문제의 답인 $x$와 $y$를 공백으로 구분해 출력한다.

1️⃣ 풀이 - 반복문

import sys
a,b,c,d,e,f = map(int, sys.stdin.readline().split())

for x in range(-999,1000):
    for y in range(-999,1000):
        if (a*x)+(b*y) == c and (d*x)+(e*y) == f:
            print(x,y)
            break

부르트포스 유형에 맞게 모든 경우의 수를 탐색하면서 결과를 찾아낸다.

2️⃣ 풀이 - 근의 공식 활용

import sys
a,b,c,d,e,f = map(int, sys.stdin.readline().split())
x = (e*c)-(b*f)) // ((a*e)-(d*b)
y = (a*f)-(d*c)) // ((a*e)-(d*b)
print(x, y)

근의 공식을 활용해 x와 y의 해를 구하는 식으로 빠르게 근의 공식의 해를 찾을 수 있다.
이렇게 하면 시간복잡도가 O(1) 으로 풀이 1번에 비해 매우 빠르다.

---

사진 출처 - 나무위키(연립방정식)