[자바] 백준 8111 - 0과 1 (java)

 문제 : boj8111

---

 

필요 알고리즘 개념

• 수학
  
  • 나머지 연산의 규칙에 대해 알고 있어야 풀 수 있다.
• 너비 우선 탐색 (BFS)
  
  • 수학적으로 풀 방법이 생각났다면, 이후 BFS를 적용해서 구현할 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  혹시 BFS를 모른다면 이 글을 참고하자.

 

  문제 조건 자체는 그리 어렵지 않다. 테스트 케이스야 동일 동작이니 일단 생각하지 말자. 그냥 1부터 시작해서(시작이 0이면 안된다고 했으므로) 0과 1을 하나씩 붙여나간 최대 100자리의 숫자가(1->10, 11->100, 101, 110, 111->...) 입력받은 N의 배수이면 그냥 출력해주면 된다!

 

  문제는, 최대 100자리의 수이니 0과 1로만 이루어져 있다고 하더라도 모든 경우가 2^99 나 된다. O(2^99)는 당연히 시간초과다. 양자컴퓨터 가져와도 몇 년 걸릴 것 같다. 그럼 문제에서 만만한 부분은 N을 가지고 뭔가 처리하는거다. N이 굳이 최대 20000밖에 안된다.

 

  배수 혹은 뭐 나누어 떨어진다 이런식의 문제라면 자주 나머지 연산의 규칙을 활용해서 풀어야 하는 경우가 많다. 이 문제도 마찬가지로 우선 아래와 같은 나머지 연산에 대한 이하의 규칙을 알고있어야 풀 수 있다. 그리고 알더라도 좀 아이디어를 생각해봐야한다. 아래 규칙을 어떤식으로 생각하면 되냐면, 51이 3으로 나누어 떨어지는지 알고 싶다. 이 때 51 = 32+19 = 2*16 + 19 이다. 여기에 각각을 3으로 나눈 나머지로 두더라도 나누어떨어지는지 알 수 있다. 2%3 = 2, 16%3 = 1, 19%3 = 1이다. 따라서 2*1+1이 되고 이건 3으로 나누어 떨어진다. 즉, 어떠한 수를 덧셈과 곱셈으로 분해해서 각각에 모듈러 연산을 취해도 전체 모듈러 연산 결과와 동일하다.

 

  이 문제의 조건은 그냥 0으로 시작하지 않는 100자리 이하의 0과 1로 이루어진 수 이다. 1에서 0과 1을 각각 붙여서 10과 11을 만들 수 있고, 거기서 또 0과 1을 각각 붙여 100, 101, 110, 111을 만들 수 있다. 이런식으로 계속 만들어갈 수 있다. 그럼 1011 = ((1*10)*10+1)*10+1 이라고 볼 수 있다. 그럼 위에서 말한대로 0과 1로 이루어진 수에 그냥 매번 0과 1을 붙이기 위해 *10+0또는 *10+1을 할 때 매번 입력받았던 N으로 나눈 나머지만 결과는 동일하다는 얘기이다. 즉, B = A*10+1 이라면 B%N == ((A%N*10%N)%N+1%N)%N 이다.

 

  이렇게되면 당연히 N으로 나눈 나머지는 항상 N보다 작은 수 이므로, 0과 1로 이루어진 100자리 수를 주어진 N 미만의 수로 표현 가능한 것이다(어차피 알고싶은건 N의 배수인지, 즉 N으로 나누어 떨어지는지 이므로). 그리고 '수를 아무거나 출력한다' 라는 조건이 있으므로 동일한 수는 한 번만 보면 된다. 무슨 말이냐면 0과 1로 이루어진 수를 계속해서 만들어나가다가, 1011을 N으로 나눈 나머지가 A였었다. 계속 만들다보니 1010101011을 N으로 나눈 나머지도 A였다. 어차피 아무거나 출력하면 된댔으니, 뒤에껀 필요가 없다! 그러므로 원래대로라면 2^99개의 어마어마한 갯수의 숫자 종류였지만, 이젠 최대 N개만 보면 되는것이다.

 

  그럼 아이디어는 생겼으니, 구현을 어떻게 할지 정해야 한다. 1부터 시작해서 0과 1을 붙여나가면 되니깐 BFS를 쓰면 적절할 것 같다. 근데 문제가 하나 생겼다! N으로 나눈 나머지만 유지하고 있는데, 이 문제는 N의 배수인 수가 존재하는지를 묻는게 아니고 그 수를 출력해야 한다. 이 처리는 지나온 길을 저장해두면 답을 찾았을 경우 시작지점까지 역산해서 해결 가능하다. 혹시 말로만 듣고 무슨말인지 모르겠다면 코드의 path 배열과 getAnswer()을 참고해보자. path[x][y] = z는 z에다가 *10+y(0또는 1)를 한 수를 N으로 나눈 나머지가 x라는 의미이다. 참고로 역산해서 찾아가는 방법이야 많으니, 별로같으면 다른 방법을 쓰면 된다.

 

  그리고 처음 N이 0과 1로만 이루어져 있다면 해당 수를 바로 출력해주면 된다. 또, 사실 짜다보니 '그러한 수가 없다면 BRAK을 출력한다.' 조건을 빠트리고 제출해버렸다. 근데 통과했다. 아마 수학적으로 저 경우 20000이하의 입력에 대해 항상 답이 존재할 것 같은데(그렇지 않았다면 BRAK이 답인 케이스는 당연히 채점 파일에 들어가 있었을 것이다) 수학이 약해 증명은 못하겠다.

 

 

로직을 정리하면..

1. N이 0과 1로만 이루어져 있다면 N을 출력한다.

2. 1부터 시작해서 매번 *10, *10+1을 해서 0과 1을 하나씩 붙여나간다. 이 때 다음 수가 어떤 수로부터 나온건지 경로와, 0과 1 중 어떤걸 붙인건지 기록해둔다.

3. '2'에서 만든 수를 매번 %N을 해서 N으로 나눈 나머지만 남긴다. 그리고 이미 나왔던 수면 무시한다.(중복체크)

4. '3'의 수가 0이 되었다면(N으로 나눈 나머지가 0이다 == N의 배수이다) '2'에서 경로 기록해둔걸 역산해서 답을 찾아 출력해준다.

5. '1'~'4'를 T번 수행하면 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int tc = Integer.parseInt(br.readLine());
        while (tc-->0) {
            sb.append(new Main().solution()).append('\n');
        }
        System.out.print(sb);
    }

    public String solution() throws Exception {
        String input = br.readLine();
        if (isInputAll0or1(input)) {
            return input;
        }
        int n = Integer.parseInt(input);

        boolean[] v = new boolean[n+1];
        int[][] path = new int[n+1][2];
        Queue<Integer> q = new ArrayDeque<>();
        q.add(1);
        v[1] = true;

        while (!q.isEmpty()) {
            int curNum = q.poll();
            if (curNum == 0) {
                return getAnswer(path);
            }
            for (int i = 0; i < 2; i++) {
                int nextNum = curNum*10 + i;
                nextNum %= n;
                if (v[nextNum]) continue;
                v[nextNum] = true;
                path[nextNum][0] = curNum;
                path[nextNum][1] = i;
                q.add(nextNum);
            }
        }
        return "";
    }

    private boolean isInputAll0or1(String input) {
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c >= '2') return false;
        }
        return true;
    }

    private String getAnswer(int[][] path) {
        StringBuilder tmp = new StringBuilder();
        for (int i = 0; i != 1; i = path[i][0]) {
            tmp.append(path[i][1]);
        }
        tmp.append(1);
        return tmp.reverse().toString();
    }
}