[종만북] CHILDRENDAY - 어린이날 (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-CHILDRENDAY

 

 

풀이

  만약 특정 자릿수(D)만을 포함하여 만든 십진수에 대해 N으로 나누어 떨어지는 가장 작은 수를 구하는 문제가 있다고 해보자. 이 경우 웰-논한 방법이 있는데, 나머지 연산의 성질을 이용하면 된다.

 

  사용할 수 있는 자릿수가 '1, 2, 3'일 경우 1을 뒤에 붙이는 경우, 2를 붙이는 경우, 3을 붙이는 경우가 있을 것이다. 이런식으로 해보면 다음과 같이 진행될 것이다. 각 단계마다 진행하다가 N으로 나눈 나머지가 0일 경우 멈추면 된다.

 

  이 때 구하려는 수를 C라 할 때, C는 엄청 커다란 수가 될 수 있다. 대충 N이 10000이므로 총 1만자리까진 가능 할 것같다. 따라서 이걸 큰 수로 계산하게 되면 시간초과가 당연하다.

 

  이 때, 현재 고른 다음 자리수를 x 라고 하자. 그리고 이전 수를 bf 라고 하자. 그럼 다음 수는 bf*10+x 일 것이다. 예를들어서 위 그림에서 11에서 112로 갈 때 bf는 11, x는 2 이다. 그리고 우리가 원하는건 나머지연산이 0이 되는걸 찾는거다. 그리고 나머지연산은 다음 두 가지 성질을 가진다.

 

  즉, 실제 연산을 진행하면 나온 '12311111222332222' 이런 어마무시한 숫자 말고, 그냥 N으로 나눈 나머지만 가지고 있어도 된다는 소리다. 또한 나눈 나머지를 가지고 방문 체크도 가능한데, 이전에 나왔던 동일한 나머지를 다시 도착한 경우 그 수는 버려도 된다(조건을 만족하는 최소의 수를 찾는게 목적이므로).

 

  따라서 위의 그림에서 N = 7인 경우, 아래처럼 나머지만 남겨놔도 된다.

  

  또한 이미 이전에 나왔던 값은 나머지를 찾는 입장에서 보면 중복 연산(방문 체크에 걸림)에 해당하므로 없애버려도 된다.

 

  그럼 다시 문제로 돌아와서, 이 문제는 N으로 나눈 나머지가 0인걸 찾는 문제가 아닌데 위의 얘기와 연관이 있을까? 이 문제를 수식으로 써보면 결국 "C를 'NX+M'(X는 1부터 무한대) 으로 나눈 나머지가 0이 되는걸" 찾는 문제이다. 이걸 좀 바꿔서 얘기하면, "C를 N으로 나눈 나머지가 M이 되는걸" 찾는 문제이다. 즉, 나누어 떨어지는 위에서 설명한 경우와 완전히 동일하게 풀 수 있다. 그냥 나눈 나머지가 0이냐 M이냐만 다를 뿐이다.

 

  또한 NX+M에서 X는 1부터라고 했으므로, C는 N+M 이상이어야 한다. 내 경우엔 N+M 미만인 값들에 대해 중복체크 하는걸 별도로 짜는게 귀찮았으므로 미리 전처리로 문제에서 제시된 D(자릿수들)를 가지고 만들 수 있는 N+M 이상인 최소값까지를 전처리로 만들어두었다. N+M은 최대 2만-1 이므로 기껏해야 6자리 수 정도라 시간복잡도에 큰 영향은 안끼친다.

private List<Integer> getStartPoints(final int limit, final int[] digits) {
    Set<Integer> v = new HashSet<>();
    List<Integer> result = new ArrayList<>();

    Queue<Integer> q = new ArrayDeque<>();
    q.add(0);
    while (!q.isEmpty()) {
        int cur = q.poll();
        if (cur >= limit) {
            result.add(cur);
            continue;
        }

        for (int digit : digits) {
            int next = cur*10+digit;
            if (v.contains(next)) continue;

            v.add(next);
            q.add(next);
        }
    }

    Collections.sort(result);
    return result;
}

  

  저 startPoints에서 시작해서 bfs를 진행하며, D에 있는 자릿수들을 붙여나가다가 나머지가 M인 곳을 찾으면 그게 답이 된다. N으로 나눈 나머지는 최대 9999 이므로, 생각보다 많이 돌지도 않는다.

// bfs
int pt = -1;
while (!q.isEmpty()) {
    int cur = q.poll();
    if (cur == remain) {
        pt = cur;
        break;
    }

    for (int digit : digits) {
        int next = cur*10+digit;
        next %= n;

        if (v[next]) continue;
        v[next] = true;
        q.add(next);
        from[next] = cur;
        select[next] = digit;
    }
}

 

  문제는 C 자체는 나머지만 출력하면 되는게 아니고, 전체 숫자를 모두 출력해줘야 한다는 점이다. 따라서 답을 찾으면 역산해서 C를 만들어내기 위해 bfs를 진행하면서 현재 나머지값이 몇일 때, D 중 어떤 값을 선택했고 직전 나머지값은 몇인지 기록을 해둬야 한다. 이 역할을 하는게 코드에서 from과 select이다. 현재 보고 있는 수를 N을 나눈 나머지가 x라 할 때, select[x]가 -1일 경우 startPoints에 해당하며 이 경우 from[x]에는 시작값을 넣어두었다. 그 이외에는 select[x]는 해당 나머지일 때 고른 자릿수, from[x]는 어떤 값으로부터 파생된 값인지를 뜻한다. 따라서 답을 구하면 역산해서 C를 구할 수 있다.

// make answer
StringBuilder tmp = new StringBuilder();
while (select[pt] != -1) {
    tmp.append(select[pt]);
    pt = from[pt];
}
tmp.reverse();

sb.append(from[pt]).append(tmp).append('\n');

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

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

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        String d = st.nextToken();
        int n = Integer.parseInt(st.nextToken());
        int remain = Integer.parseInt(st.nextToken());

        int[] digits = sortedDigits(d);
        List<Integer> startPoints = getStartPoints(n+remain, digits);
        if (ifFinish(startPoints, n+remain)) return;

        int[] from = new int[n];
        int[] select = new int[n];
        boolean[] v = new boolean[n];
        Queue<Integer> q = new ArrayDeque<>();

        // init queue using startPoints
        for (int cur : startPoints) {
            int mod = cur % n;
            if (mod == remain) {
                sb.append(cur).append('\n');
                return;
            }

            if (v[mod]) continue;
            v[mod] = true;
            q.add(mod);
            from[mod] = cur;
            select[mod] = -1;
        }

        // bfs
        int pt = -1;
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (cur == remain) {
                pt = cur;
                break;
            }

            for (int digit : digits) {
                int next = cur*10+digit;
                next %= n;

                if (v[next]) continue;
                v[next] = true;
                q.add(next);
                from[next] = cur;
                select[next] = digit;
            }
        }

        if (pt == -1) {
            sb.append("IMPOSSIBLE").append('\n');
            return;
        }

        // make answer
        StringBuilder tmp = new StringBuilder();
        while (select[pt] != -1) {
            tmp.append(select[pt]);
            pt = from[pt];
        }
        tmp.reverse();

        sb.append(from[pt]).append(tmp).append('\n');
    }

    private boolean ifFinish(final List<Integer> startPoints, final int target) {
        if (startPoints.isEmpty()) {
            sb.append("IMPOSSIBLE").append('\n');
            return true;
        }

        if (startPoints.get(0) == target) {
            sb.append(target).append('\n');
            return true;
        }

        return false;
    }

    private static int[] sortedDigits(final String d) {
        int[] digits = new int[d.length()];
        for (int i = 0; i < d.length(); i++) digits[i] = -(d.charAt(i)-'0');
        Arrays.sort(digits);
        for (int i = 0; i < d.length(); i++) digits[i] = -digits[i];
        return digits;
    }

    private List<Integer> getStartPoints(final int limit, final int[] digits) {
        Set<Integer> v = new HashSet<>();
        List<Integer> result = new ArrayList<>();

        Queue<Integer> q = new ArrayDeque<>();
        q.add(0);
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (cur >= limit) {
                result.add(cur);
                continue;
            }

            for (int digit : digits) {
                int next = cur*10+digit;
                if (v.contains(next)) continue;

                v.add(next);
                q.add(next);
            }
        }

        Collections.sort(result);
        return result;
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.