[백준 - 1009] 분산처리 - Java

문제 설명

 

1009번: 분산처리

 

풀이 1 : Fail(정수 오버플로우 발생)

소스 코드

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            long dataCnt = (long) Math.pow(a, b);
            if(dataCnt%10==0) System.out.println(10);
            else System.out.println(dataCnt%10);
        }
    }
}​

 

 

문제 원인

데이터의 개수가 데이터의 개수가 10의 배수일 경우 10을 출력하도록 했고 x1~x9일 때는 각각 1~9를 반환하도록 했다. 하지만 주어진 문제의 입력 정수 a의 최대값은 99, b는 999999이다. 즉, 데이터의 개수는 99^999999개가 나올 수 있는 것이다. 현재 코드에서는 이러한 연산을 직접하고 있으므로 당연히 정수 오버플로우가 발생하게 된다.

 

풀이 2 : Fail(메모리 초과)

소스 코드

import java.math.BigInteger;
import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            BigInteger base = BigInteger.valueOf(a);
            BigInteger dataCnt = base;
            for (int j = 1; j < b; j++) dataCnt = dataCnt.multiply(base);

            if(dataCnt.remainder(BigInteger.valueOf(10)).equals(BigInteger.valueOf(0))) System.out.println(10);
            else System.out.println(dataCnt.remainder(BigInteger.valueOf(10)));
        }
    }
}

 

문제 원인

이번에는 데이터의 개수를 무한대로 표현할 수 있도록 BigInteger 객체를 이용했다. 하지만 BigInteger는 문자열을 사용하는데 99^999999의 수를 문자열로 표현하는데 엄청난 메모리를 사용하게 되어 결과는 메모리 초과가 발생했다.

 

풀이 3 : Success

소스 코드

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            b %= 4;
            if(b==0) b = 4;
            int share = 1, result = 0;
            for (int j = 0; j < b; j++) {
                share *= a;
                result = share;
            }
            if(result%10==0) System.out.println(10);
            else System.out.println(result%10);
        }
    }
}​

 

접근 방법

앞서 2개의 풀이를 통해 해당 문제는 "데이터의 개수를 구하는 연산" 자체를 하면 안된다는 것을 알 수 있다. 왜냐하면 정수로도 표현 못하고 문자열로도 표현 못하기 때문이다.

 

그리하여 일종의 규칙성을 찾아내어 정답을 도출하는 방법밖에 없다. 입력받는 a의 값에 따라 나름 규칙성을 찾아보았는데 다음과 같았다.

 

행의 값 : a, 열의 값 : b

2 4 8 16 / 32 64 128 256 / ...

3 9 27 81 / 243 729 2187 6561 / ...

4 16 64 256 / 1024 , ...6, ....

5 25 125 ..5 / ..5, ...

6 36 216 ...6 / ...6, ....

7 49 343 3401 / ...7, ...

8 64 512 4096 / ...8, ...

9 81 729 6561 / ...9, ...

 

위 규칙성을 보면 a의 값이 2~9별로 최소 2개씩, 최대 4개씩 끝 자리수가 반복되고 있다는 것을 알 수 있다. a가 1일 경우는 항상 1을 출력하고 a가 10일 때는 항상 10을 출력해주어야되기 때문에 고려하지 않았다.

따라서 데이터의 총 개수가 a^999999일지라도 우리는 a의 최대 4승의 데이터까지만 구해도 정답을 도출할 수 있다. 이를 위해 b의 값을 for문을 돌기전에 별도로 초기화 해주었다.

 

 

참고 자료

• https://www.acmicpc.net/problem/1009