DAY1 초급 - 백준 19575번 (C++)

www.acmicpc.net/problem/19575

19575번: Polynomial

 

<답안>

#include <iostream>
using namespace std;
int main()
{
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    long long N,X,ai,i;
    long long before;
    bool first = true;
    
    cin>>N>>X;
    while(N >= 0)
    {
        cin>>ai>>i;
        if(first)
        {
            before = ai;
            first = false;
        }
        else
        {
            before = ((before * X) + ai);
            before = before%1000000007;
        }
        N--;
    }
    cout<<before<<"\n";
    return 0;
}

 

<설명>

문제를 이해하는데는 그렇게 어렵지만은 않았지만 자료형 크기와 오버플로우를 생각하기에 좋은 문제였다

 

입력 예시인 10x3승 + 3x2승 + 9x1승 + 3 을 잘 형태를 변환해보면 x(x(10x + 3) + 9) + 3 이 될수있다

그럼 느낌상으로도 뭔가 괄호가 전에 먼저 계산되어 있고, 그 값에 x를 곱한 다음 + 상수를 하면 되는게 느껴질 것이다

그래서 이전값을 before 라는 이름으로 저장한다

 

여기서 맨 처음 입력(N차항)의 경우는 초기 before 값을 설정해주어야 한다

그래서 before 를 입력된 계수값인 ai로 설정해준다

그 다음번 부터는 before = before * X + ai 값으로 계산을 해주면 된다

 

여기서 곱해지는 과정이 있기 때문에 오버플로우가 발생할 수가 있다

그렇기 때문에 문제의 조건에 있는 1000000007로 나눈 나머지값으로 항상 정정해주어야 한다

그렇기 때문에 자료형도 int가 아닌 long long으로 맞춰주어야만 정상적으로 진행이 된다

 

그렇게 계산된 before 값을 최종적으로 출력한다