백준 1009 - 분산처리

 

---

[풀이]

Math.pow(a,b)로 접근할 경우 숫자가 너무 커지게 되어 오류가 생긴다

 

그래서 두 가지 접근 방법을 떠올려보았다

 

1) a의 일의 자릿수만 가지고 b번 곱해보자! 👉 b번 곱해도 숫자가 커지지 않을까 :( 👉 나머지 연산자

2) 제곱수.. 규칙이 있을 것만 같다!

 

여기서 어째선지 2)번을 택했더란다. 1)도 구현해보긴 했다😅

 

일단 [0,9] 제곱수가 최대 4개의 반복 양상을 보여 배열로 생성해 주었다. -> int chart[10][4] 생성

 

이때, 각 행의 0, 1, 2, 3 번째는 b값이 4n, 4n+1, 4n+2, 4n+3일 때와 매핑되므로 순서를 유의해서 생성한다

ex: chart[3] = new int[]{1, 3, 9, 7};

 

a=12, b=10 인 경우 :

newA = 2 (a%10 : 1의자리 수) , newB = 2 (b%4 : 제곱의 중복을 줄여줌)으로 치환되어 chart[2][2]인 4를 리턴한다.

 

 

** 반환값이 0의 경우 (ex : a=10n) 10번째 컴퓨터가 되어야 하므로 10을 리턴해 주어야 한다.

---

[소스코드]

 

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class N1009 {
    static int[][] chart = new int[10][4];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer buf = new StringBuffer();
        int testCase = Integer.parseInt(br.readLine());
        StringTokenizer tok;

        chart[0] = new int[]{0, 0, 0, 0};
        chart[1] = new int[]{1, 1, 1, 1};
        chart[2] = new int[]{6, 2, 4, 8};
        chart[3] = new int[]{1, 3, 9, 7};
        chart[4] = new int[]{6, 4, 6, 4};
        chart[5] = new int[]{5, 5, 5, 5};
        chart[6] = new int[]{6, 6, 6, 6};
        chart[7] = new int[]{1, 7, 9, 3};
        chart[8] = new int[]{6, 8, 4, 2};
        chart[9] = new int[]{1, 9, 1, 9};

        for (int i = 0; i < testCase; i++) {
            tok = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(tok.nextToken());
            int b = Integer.parseInt(tok.nextToken());
            int val = findVal(a, b);
            buf.append((val == 0 ? 10 : val) + "\n");
        }
        System.out.println(buf.toString());
    }

    static int findVal(int a, int b) {
        int newA = a % 10;
        int newB = b % 4;
        return chart[newA][newB];
    }
}

//findVal->findValPow로 교체(반복문)
static int findValPow(int a, int b) {
    int ans = 1;
    for (int i = 0; i < b; i++) {
        ans *= a;
        ans %= 10;
    }
    return ans;
}

 

---

[실행 결과]

실행 결과

findValPow(int,int) : 984ms

findVal(int,int) : 144ms

 

확실히 반복문이 시간이 더 오래 걸리는 것을 알 수 있었다.

---

[후기]

 

좀 무식하게 짠 것 같다 😔

다른 풀이를 보니, 제곱수의 규칙을 정해 케이스를 나누어 풀이하는 방법도 있는 듯하다.