백준 - 분산처리 (통과 못하면 처음부터 꼼꼼히 보자)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/1009

[문제 설명]

데이터를 1개씩 컴퓨터들이 입력 받는다. (컴퓨터는 10대)

a^b번째 데이터를 맡은 컴퓨터는 몇번째 컴퓨터인가?

[접근 방법]

a^b이라고 해서 계산을 다할 필요는 없어보인다. 이 문제를 풀기 위해서는 두 가지가 필요하다.

첫째로, 1의 자리는 1의 자리의 연산에 의해 결정된다(소수점이 없을 때). 따라서 1의 자리를 b번 곱한 것을 고르면 된다.

예를 들어, 2이든 12이든 102이든 2342이든 13532152이든 b번 제곱하면 같은 일의 자리숫자를 가진다.

또한, 일의 자리의 제곱의 결과는 사이클을 가지고 있다.

1은 몇번 곱해도 1

2는 2,4,8,6

3은 3,9,7,1 

이러한 두 가지 성질을 이용하면 숫자를 제곱할 필요 없이 답을 구할 수가 있다.

시간복잡도는 O(N)

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    static int[][] possibleNums = {
            {10}
            ,{1}
            ,{2,4,8,6}
            ,{3,9,7,1}
            ,{4,6}
            ,{5}
            ,{6}
            ,{7,9,3,1}
            ,{8,4,2,6}
            ,{9,1}
    };
    public static void main(String[] args) throws Exception {
        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (int lineNumber = 1; lineNumber <= N; lineNumber++) {
            String[] inputs = br.readLine().split(" ");
            int a = Integer.parseInt(inputs[0])%10;
            // 배열은 0부터 시작이므로 1을 빼줌
            int b = Integer.parseInt(inputs[1])-1;
            System.out.println(possibleNums[a][b%possibleNums[a].length]);
        }
    }
}

이 문제에 진짜 엄청 많은 시간을 뺏겼다. 무엇 때문이었을까?

바로 possibleNums[0][0]의 값을 0으로 둔 것이다.

이 결과 10,20,90,100,200 등과 같이 일의 자리가 0인 애들이 원래 10이 나와야 하는데 결과가 0으로 나온 것이다.

일의 자리수에 너무 집중해서 본질을 잃고 초기 조건을 꼼꼼히 보지 않아서 발생한 문제 같다.

물론 인텔리제이에서 입력을 계속 더 받아서 로직이 아닌 다른 데에 문제가 생겼다고 생각한 게 컸지만, 그래도 코드를 처음부터 면밀히 다시 봤다면 빨리 수정할 수 있는 문제였다.

요즘 그래도 무지성 제출하지 않고 다시 생각하고 짜는 습관을 들였는데, 이번 문제를 보고 헤이해졌다는 느낌을 받았다.

앞으로 제출 전에 로직 체크, 만약에 제출했는데 틀렸다면 뭐가 확실히 틀렸는지 로직을 먼저 눈으로 코드 처음부터 파악해야겠다.