[Softeer/소프티어] 수퍼 바이러스 - 자바[Java]

https://softeer.ai/practice/6292

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

 

 

풀이

k * (p^10n) 을 구하는 문제다.

다만 k, p,가 최대 10^8이 될 수 있고 n은 10^16이 입력으로 들어올 수 있기 때문에 k * (p^10n)을 아래 풀이와 같이 직접 구하면 시간초과가 뜬다.

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


public class Main
{
    // k * p^10n
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int k = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        Long n = Long.parseLong(st.nextToken());

        n *= 10;

        while (n > 0) {
            k *= p;
            k %= 1000000007;
            n--;
        }

        System.out.println(k);
    }
}

 

그래서 재귀함수를 이용한 분할정복을 사용해야 한다.

f(2, 10) = f(2, 5) * f(2, 5)
f(2, 5) = f(2, 2) * f(2, 2) * 2
f(2, 2) = f(2, 1) * f(2,1)
f(2, 1) = 2

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int k = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        long n = Long.parseLong(st.nextToken());

        n *= 10;

        long result = virus(p, n);
        System.out.println(k * result % 1000000007);
    }

    static public long virus(int p, long n) {
        if (n == 1) {
            return p;
        }

        long half = virus(p, n/2);

        if (n % 2 == 0) {
            return half * half % 1000000007;
        } else {
            return (half * half % 1000000007) * p % 1000000007;
        }
    }
}

• n의 입력 범위가 크기 때문에 n을 long으로 입력받는다.
• n에 10을 곱한 다음, virus(p, n)을 호출한다.

virus() 메서드를 보면, 계속해서 곱셈 결과를 1000000007로 나눈 나머지를 반환하는데, 이렇게 해도 정답을 구할 수 있는 이유는 모듈로 사칙 연산 때문이다.

 

모듈로 연산 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈)

덧셈, 뺄셈, 곱셈에 대해서는 다음 식이 항상 성립한다. (이부분에서는 mod M을 % M이라고 표현)

• 덧셈 : (a+b) % M = ((a % M) + (b % M)) % M
• 뺄셈 : (a-b) % M = ((a%M) - (b%M)) % M
• 곱셈 : (a*b) % M = ((a%M) * (b%M)) % M

 

최종적으로 출력할 값은 최종 바이러스 개수를 1000000007로 나눈 나머지이므로, 곱셈을 할 때마다 1000000007로 나눈 나머지값을 구해서 반환하면 정답을 구할 수 있다.

 

Reference

• [알고리즘] Divide and Conquer (분할정복)
• [알고리즘] 분할정복 방법 - 이진 탐색, 퀵 정렬 알고리즘
• 모듈로 연산(modulo operation)