백준 19575번 Polynomial JAVA 구현해보기

---

```

백준 19575번 Polynomial JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1. 백준 19575번 Polynomial 풀이

---

https://www.acmicpc.net/problem/19575

19575번: Polynomial

 

 

 

백준 19575번 Polynomial은

난이도 브론즈 등급의 문제로서

 

미지수 x로 구성된 다항식 연산을 빠르게 계산해보는 문제입니다.

예를 들어서

x^3 + 2* x^2 + 5* x^1 + 12*x^0 은

x(x(x+2)+5)+12로 계산을 하면 연산 횟수 가줍니다.

 

첫째줄에

다항식의 차수, 미지수 x의 값이 주어지고

두 번째 줄부터 N+2 번째 줄까지 각 항에 대해 계수와 차수가 주어질 때

다항식을 평가한 후 10^9 + 7로 나눈 답을 출력해주면 됩니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

for문을 돌려서 순서대로 대해주고

mod로 나눈 다음 출력을 해주면 됩니다.

오랜만에 출력방법으로 BufferedWriter를 한번 써봤습니다.

 

방법 1

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 다항식의 차수 degree of polynomial (degP)
        final int degP = Integer.parseInt(st.nextToken());
        // 평가할 값인 정수 variable (x)
        final int x = Integer.parseInt(st.nextToken());
        // 결과값 sum
        long sum = 0L;

        for (int i = 0; i <= degP; i++) {
            // 입력을 받는다.
            st = new StringTokenizer(br.readLine());
            final int coefficient = Integer.parseInt(st.nextToken());
            //final int degree = Integer.parseInt(st.nextToken());
            if (i == 0){
                sum = coefficient;
            }
            else {
                // 중간 연산값 intermediate operation value (sum)
                // 다항식을 평가한 후 10^9 + 7로 나눈 나머지를 출력
                sum = (coefficient + sum * x) % 1000000007;
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
    }
}

//codemasterkimc.tistory.com [김씨의 코딩 스토리]

 

for 문 안에 if문을 추가로 돌리면 속도가 느려지기 때문에

조금이라도 빠르게 하고자 마지막 상수값을 더하는 부분을 밖으로 빼고 if문을 삭제하였습니다. 

 

방법 2

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 다항식의 차수 degree of polynomial (degP)
        final int degP = Integer.parseInt(st.nextToken());
        // 평가할 값인 정수 variable (x)
        final int x = Integer.parseInt(st.nextToken());
        // 결과값 sum
        long sum = 0;

        for (int i = 0; i < degP; i++) {
            // 입력을 받는다.
            st = new StringTokenizer(br.readLine());
            final int coefficient = Integer.parseInt(st.nextToken());
            // final int degree = Integer.parseInt(st.nextToken());
            // 중간 연산값 intermediate operation value (sum)
            sum = x * (coefficient + sum) % 1000000007;
        }

        // 마지막 상수는 곱하지 않는다.
        st = new StringTokenizer(br.readLine());
        final int coefficient = Integer.parseInt(st.nextToken());
        // final int degree = Integer.parseInt(st.nextToken());
        // 다항식을 평가한 후 10^9 + 7로 나눈 나머지를 출력
        sum = (sum + coefficient) % 1000000007;
        System.out.print(sum);
    }
}

//codemasterkimc.tistory.com [김씨의 코딩 스토리]

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---