| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 246 | 94 | 84 | 41.379% |
문제
지학이는 3차 다항식(cubic polynomial)을 좋아하는 잘 알려진 cubelover 이다.
어느 화창한 봄날, 지학이는 아파트 놀이터에서 승현이가 길이 n의 정수 수열 x1, x2, ..., xn 을 가지고 노는 것을 보았다. 지학이는 그 아파트의 짱이었고, 승현이보다 45일이나 먼저 태어난 형이었다. 지학이는 승현이를 보자 마자 갖고 놀던 수열을 빼앗아 갔다.
승현이는 그 자리에서 엉엉 울기 시작했고, 마음이 약해진 지학이는 승현이가 1 ≤ i ≤ n인 모든 정수 i에 대해 xi = ai³+bi²+ci+d를 만족하는 실수 a, b, c, d 를 찾으면 수열을 돌려주겠다고 약속했다. (사실 3차 다항식이라 a ≠ 0이어야 하긴 하는데, 지학이는 그 정도로 엄밀하게 굴고 싶진 않은 모양이다.)
간만에 학교를 나와 외출을 즐기고 있는 당신은, 울고 있는 승현이와 눈을 마주쳤다. 승현이는 여러분에게 곧장 달려와서, 빨리 그러한 실수 a, b, c, d 를 찾아달라고 졸랐다. 당신은 과연 승현이의 눈물을 닦아 줄 수 있는가?
입력
이 문제는 한 입력에 여러 개의 테스트 케이스가 주어진다. 첫 번째 줄에 그러한 테스트 케이스의 개수 T (1 ≤ T ≤ 1000) 가 주어진다.
이후 T개의 줄이 주어진다. 첫 번째로 수열의 길이인 정수 n (1 ≤ n ≤ 500) 이 주어진다. 이후 n 개의 정수가 주어진다. 이 중 i번째 정수는 xi (0 ≤ xi ≤ 50, 000, 000) 를 뜻한다.
출력
T개의 줄에 걸쳐, 만약에 승현이가 원하는 실수 a, b, c, d가 존재한다면 YES, 존재하지 않는다면 NO를 출력한다.
접근
아주 개 빡치는 문제였다.
1 1 1 1
8 4 2 1
27 9 3 1
64 16 4 1
이 행렬의 역행렬을 [X1, X2, X3, X4]에 곱해서 해결하려 했는데,
실제로 numpy에서 역행렬을 구해서 C++로 옮겨서 써보니, 실수형의 처리 때문인지 오답이 나왔다.
그래서 직접 연립방정식을 선형대수학의 가우스 소거법으로 풀었다.
하단 첨부한 그림을 참고하면 된다.
마지막에 구한 식에서 제일 왼쪽 행렬이 항등행렬이 되도록 각각 아래행들을 빼주면 된다.
풀이
N이 4 이하이면, 무조건 풀리는 방정식이기에 YES를 바로 출력한다.
a, b, c, d에 각 식을 넣어준다.
그리고 주의해야 되는 점은 연산 마지막에 0.000001의 작은 수를 더하고 int로 형변환을 해주어야 된다.
프로그래밍 언어에서 실수형을 다루는 것은 너무 귀찮은 일이다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
ll T, N, X[501];
long double a, b, c, d;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN(T);
while (T--)
{
CIN(N);
FUP(i, 1, N) CIN(X[i]);
if (N <= 4)
{
COUT("YES\n");
continue;
}
d = -X[4] + 4 * X[3] - 6 * X[2] + 4 * X[1];
c = (2 * X[3] - 9 * X[2] + 18 * X[1] - 11 * d) / 6;
b = -(X[2] - 8 * X[1] + 6 * c + 7 * d) / 4;
a = X[1] - b - c - d;
//cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
string ans = "YES\n";
FUP(i, 5, N)
{
if ((int)(a * pow(i, 3) + b * pow(i, 2) + c * i + d + 0.000001) != X[i])
{
ans = "NO\n";
break;
}
}
COUT(ans);
}
return 0;
}