[C언어] Polynomial Multiplication (단순 구현인데 구조체를 곁들인)

문제

Polynomial Multiplication

두 다항식 f(x)와 g(x)의 계수들을 입력으로 받아서 두 다항식을 곱해서 나온 다항식의 계수들을 출력해주세요. 입력으로는 첫 줄에서 f(x)와 g(x)의 최고 차항의 차수 n과 m을 입력받고, 다음 줄에서는 f(x)의 각 항의 계수, 마지막 줄에서는 g(x)의 각 항의 계수를 입력받으세요.

• 입력의 한 행에서 각 항목은 공백으로 구분해주세요.
• 예시 구조체가 poly.h에 정의되어 있습니다. 참고하여 자유롭게 변형하셔도 좋습니다.
• 반드시 구조체를 활용하여 문제를 풀어주세요.
• 각 계수는 정수라고 가정합니다.

 

입출력 예시

(입력 #1)

2 2
2 3 8
6 7 3

(출력 #1)

12 32 75 65 24

 

(입력 #2)

3 2
2 3 -8 1
6 -7 3

(출력 #2)

12 4 -63 71 -31 3

 

어떻게 풀까?

구조체를 쓰라고 하였으니 계수를 받을 배열을 저장할 구조체를 만들자.

그리고 우리가 다항식 계산을 하는 방식을 생각해보면

이런 구조로 하고 있다고 볼 수 있다.

게다가 곱을 진행하고 차수를 찾는 방법은 지수를 이용하면 된다.

해당 인덱스의 값은 해당 계수의 차수와 같다.

그러니 곱한 계수의 값은 인덱스의 합의 위치로 더해주면 간단히 구현할 수 있다.

 

코드를 살펴보자

#include <stdio.h>
#define ll long long
typedef struct{
	ll fx[1010];
	ll gx[1010];
}func;
func fun;
ll hx[1010]={0};
int main(int argc, char *argv[]) {
	int f,g;
	scanf("%d",&f);
	scanf("%d",&g);
	for(int i=0; i<=f; i++)
	{
		scanf("%lld",&fun.fx[i]);
	}
	for(int j=0; j<=g; j++)
	{
		scanf("%lld",&fun.gx[j]);
	}
	for(int i=0; i<=f; i++)
	{
		for(int j=0; j<=g; j++)
		{
			hx[i+j] += fun.fx[i]*fun.gx[j];
		}
	}
	for(int i=0; i<=f+g; i++)
		printf("%lld ",hx[i]);
	printf("\n");

	return 0;
}

 

설명했던것처럼 계수를 받고 계산하는 과정대로 하였다.

다만 약간 다른 점은 scnaf로 받는 과정에서 f와 g로 받은 최대 차수부터 받지 않고 0번 인덱스부터 받아서

출력시에 거꾸로 출력해주는 점이지만 결국 같은 연산이기 때문에 큰 차이가 없다.