[Python] 27295번 선형 회귀는 너무 쉬워 1

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

27295번: 선형 회귀는 너무 쉬워 1

---

 

23/01/30

 

 

선형 회귀는 너무 쉬워 시리즈의 첫 번째 문제이다. 간단한 선형 방정식을 풀면 되는 문제다.

---

 

문제 접근 방식:

 

 

문제의 요구 사항은 $b$가 주어지고 각 데이터들이 주어질 때, $\sum_{i=1}^{n} (ax_i + b - y_i)$가 $0$에 가장 가깝도록 하는 $a$의 값을 구하는 것이다.

 

가능한 $a$의 값이 여러 개라면 EZPZ를 출력하면 된다.

 

식을 좀 정리하면 $a \sum_{i=1}^{n} x_i + nb - \sum_{i=1}^{n} y_i$이 $0$에 가깝도록 하는 $a$를 구하면 된다.

 

$\sum x_i = 0$이라면 $a$값과 상관 없이 이 식의 값이 항상 일정하다. 즉, $a$의 값이 여러 개가 된다.

 

따라서 이 경우에서는 EZPZ를 출력하면 된다.

 

$\sum x_i \neq 0$이라면 저 식을 $0$으로 만드는 $a$의 값은 일차 방정식을 풀어서 해결할 수 있다.

 

이때, $\sum y_i - nb = p$, $\sum x_i = q$라고 하면, $a = p/q$가 된다.

 

기약 분수로 출력해야 하므로, $p$와 $q$의 $\mathrm{gcd}$를 유클리드 호제법을 사용하여 구하고, 이를 각 수에 나누어서 출력 형식을 잘 지켜 출력하면 맞았습니다를 받을 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

import sys
input = sys.stdin.readline
from math import gcd
# B번
n, b = map(int, input().rstrip().split())
sum_x = 0
sum_y = 0
for _ in range(n):
    x, y = map(int, input().rstrip().split())
    sum_x += x
    sum_y += y
if sum_x == 0:
    print('EZPZ')
else:
    p = sum_y - n*b
    q = sum_x
    k = gcd(abs(p), abs(q))
    if p%q == 0:
        print(p//q)
    elif q < 0:
        print(f'{-p//k}/{-q//k}')
    else:
        print(f'{p//k}/{q//k}')