[소프티어] 바이러스 레벨2 자바 풀이

https://softeer.ai/practice/6284

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

 

 

바이러스 문제는 수학 계산 문제이다. K * P^N 만 계산하면 된다.

처음에 간단한 문제라고 생각하고 풀었다가 계속 실패가 나왔다. 

틀린 코드

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

public class Main {

    private static int K;
    private static int P;
    private static int N;
    private static double dap = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        K = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        // K * P^N
        dap = K * Math.pow(P, N);

        dap %= 1000000007;
        
        bw.write(dap + "\n");

        bw.flush();
        bw.close();
    }
}

몇가지 문제가 생겼다.

• Math.pow()는 부동 소수점 연산을 하기에 아주 큰 값을 계산할 때는 정밀도 손실이 발생한다. 
• 여기에서는 거듭제곱을 많이 수행하는데  정수형 변수에 저장하면 범위를 초과하여 오버플로우가 발생한다.

정답 코드

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

public class Main {
	
    private static int K;
    private static int P;
    private static int N;
    private static long dap = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        K = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        // K * P^N

        // 방법 1 (틀림)
        // dap = K * (long) Math.pow(P, N);
        //
        // dap %= 1000000007;

        // 방법 2
        dap = K;
        for (int i = 0; i < N; i++) {
            dap = (dap * P) % 1000000007;
        }

        bw.write(dap + "\n");

        bw.flush();
        bw.close();
    }
}

큰수 이기에 문제에서가 힌트가 있었다.

최종 결과를 1,000,000,007로 나눈 나머지를 요구

• 모듈러 연산을 했다.
• 정답을 저장하는 변수의 자료형도 double -> long 으로 변경 (int는 오버플로우 발생함)

 

오버플로우와 정밀도를 모두 신경쓰게 되는 문제였다.