[BOJ C++] 백준 27295번: 선형 회귀는 너무 쉬워 1

 📚 문제

[BOJ C++] 백준 27295번: 선형 회귀는 너무 쉬워 1
https://www.acmicpc.net/problem/27295

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 수식 때문에 어려워 보이는 문제이지만, 천천히 이해해보면 생각보다 쉬운 문제이다.
• 서론이 길지만 결국 문제는 $\displaystyle\sum_{i=1}^{n} (a_1x_i + b - y_i)^1$의 값이 0이 되는 $a_1$ 값을 구하는 것이다.
• 시그마를 풀어서 써보면 다음 수식을 얻을 수 있다.
  $a_1(x_1+x_2+x_3+...+x_n) + nb - (y_1+y_2+y_3+...+y_n)$
  즉, $a_1(x_1+x_2+x_3+...+x_n) + nb - (y_1+y_2+y_3+...+y_n) = 0$을 만족하는 $a_1$값을 구하면 되므로
  $a_1(x_1+x_2+x_3+...+x_n) = (y_1+y_2+y_3+...+y_n) - nb$,
  $a_1 = \frac{(y_1+y_2+y_3+...+y_n) - nb}{(x_1+x_2+x_3+...+x_n)}$임을 알 수 있다.
• xsum에는 x값의 합을, ysum에는 y값의 합을 저장한다.
  각 x값과 y값은 $-10^9 \leq x_i, y_i \leq 10^9$이므로 long long형을 사용한다.
  또, xsum=0인 경우, $a \times 0 = 0$과 같은 식이 되므로 이를 만족하는 a값은 무수히 많다. 이 경우에는 "EZPZ"를 출력한다.
• 이후에는 ysum을 분자값, xsum을 분모값으로 생각하여 계산한다. 분모(xsum)가 음수인 경우, 1/-3가 아닌 -1/3과 같은 형식으로 나타내기 위해 xsum을 양수로, ysum을 음수로 바꾼다.
• 유클리드 호제법을 사용하여 분자와 절댓값과 분모의 절댓값의 최대공약수를 구하고, 각각을 구한 최대공약수로 나누어 약분한다. 분모가 1인 경우, 분모를 생략할 수 있으므로 분자만 출력하고, 그렇지 않은 경우에는 "분자/분모" 형태로 출력한다.

---

 ⌨️ C++ 코드

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

long long gcd(long long a, long long b) { // 최대공약수 구하는 함수.
    if (a < b) swap(a, b);
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, b, xsum = 0, ysum = 0, g;
    cin >> n >> b;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        xsum += x;
        ysum += y;
    }
    if (!xsum) {  // a*0 형태라 a 값이 무수히 많은 경우.
        cout << "EZPZ";
        return 0;
    }
    ysum -= n * b;
    g = gcd(abs(ysum), abs(xsum));  // 두 수의 최대공약수 구하기.
    ysum /= g;
    xsum /= g;
    if (xsum < 0) {  // 분모가 음수인 경우, 분자와 분모의 부호 변경.
        ysum = -ysum;
        xsum = -xsum;
    }

    if (xsum == 1)  // 분모가 1이면 생략.
        cout << ysum;
    else
        cout << ysum << '/' << xsum;
}