A. 문제설명
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXCjsn0KJzcDFAX0
문제에 대한 자세한 설명은 링크 참조
1. 위와 같은 다항식이 존재
2. f0~fN에 대한 정의가 각각 주어지고, 이를 정의하는 ti, ai, bi가 주어질 때 fi(x)를 구할 것
- ti =1이면 fi(x) = fai(x) + fbi(x)
- ti =2이면 fi(x) = ai × fbi(x)
- ti= 3이면 fi(x)= fai(x) × fbi(x)
3. M개의 수 x1,x2, ⋯, xM이 주어질 때,fN(x1), fN(x2), ⋯, fN(xM)을 계산하라
B. 접근법
다이나믹 프로그래밍
우선 문제에 대한 구현을 시작하기 이전에 해당 다항식 정의에 대한 이해가 필요하다.
다항식의 정의를 두가지로 나누어 생각하는 것이 이해하기에 편한데, 1. 함수 f0~fN은, 즉 fN은 fN-1에 의해 정의되는 점화식이라는 것 2. ti=1~3에 따라 f는 정의되는 식의 종류가 3개라는 것
위 두가지를 이해하고 f에 대한 구현을 충실히 하면 된다.
C. 풀이
1. 함수 f에 대한 정의를 ti의 값에 따라 3가지로 나누어 정의
2. 함수 f를 정의하는 인자 ti, ai, bi는 구조체 배열로 정의
3. Base case인 f0(x), f1(x)를 제외하고 점화식에 대한 평가를 f2(x)부터 fN(x)까지 수행
4. 마지막으로 이전에 구해진 fN-1(x) 함수들을 기반으로 fN(x) 값을 구함
D. 내 코드
