[자바] 백준 22943 - 수 (java)

문제 : boj22943

---

 

필요 알고리즘 개념

• 브루트포스
  • 가능한 모든 경우에 대해 완전탐색을 통해 경우의 수를 찾아줄꺼다.
• 에라토스테네스의 체
  • 소수 판정 알고리즘이다. 한 개의 수가 소수인지 판정할때는 안쓰인다. 이 문제에서는 특정 범위 이내의 모든 소수를 찾아두고 풀이를 진행할 것이므로 에라토스테네스의 체를 사용했다.

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

 

---

 

풀이

  우선 이 문제를 풀기위해 알아야 하는 것들을 생각해보자.

1. 0부터 9까지 K가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수

  예를들어 K가 3이라면 123, 451, 294, ... 등등 0~9를 3개 사용해서 만들 수 있는 모든 수를 만들 수 있어야 한다. 브루트포스 알고리즘은 이 때 사용할 것이다. K가 최대 5이므로 시간복잡도는 최대 O(10^5)이 필요하다. 사람이 직접하긴 어렵지만 컴퓨터에겐 아주 이-지한 수준이다.

 

2. 서로 다른 두 소수의 합들

  어차피 K는 최대 5 이므로 최대로 만들 수 있는 값은 '98765'이다(0부터 9까지 5(=K의 최대값)가지의 숫자를 한 번씩 사용해서 만들 수 있는 가장 큰 수). 따라서 98765 이하의 모든 소수의 합 중 98765이하의 합들을 알 수 있어야 한다.

 

3. 두 소수의 곱들

  마찬가지로 98765 이하의 모든 소수의 곱 중 98765 이하의 곱들을 알 수 있어야 한다. 합과 달리 서로 같아도 된다.

 

 

 

  그럼 위의 3가지를 알기 위해 풀이를 진행해보자.

A. 에라토스테네스의 체로 소수 판정

  우선 '2'와 '3'을 알기 위해서는 98765 이하의 모든 소수를 알 수 있어야 한다. 에라토스테네스의 체 알고리즘을 통해 구하고, ArrayList 등의 자료구조에 담아둔다. 혹시 에라토스테네스의 체를 모른다면 공부해두자. 소수 판정 문제에서 엄청 자주 사용된다. 코드의 initPn()을 참고하자. 이 때, 98765의 제곱근까지만 반복문을 돌리며 확인하는걸 볼 수 있다. 그 이유는 이 글을 참고하자.

private void initPn() {
    boolean[] isPn = new boolean[LIMIT+1];
    int sqrtN = (int)Math.sqrt(LIMIT);
    for (int i = 3; i <= sqrtN; i+=2) {
        if (isPn[i]) continue;
        int base = i+i;
        while (base <= LIMIT) {
            isPn[base] = true;
            base+=i;
        }
    }
    pn.add(2);
    for (int i = 3; i <= LIMIT; i+=2) {
        if (!isPn[i]) pn.add(i);
    }
}

 

 

B. 소수의 합과 곱들을 미리 계산해두자.

  '2'와 '3'을 미리 계산해서 HashSet에 넣어둔다면 이후 O(1)로 어떠한 특정 값이 소수의 합과 소수의 곱을 동시에 만족하는지 확인할 수 있을 것이다.(최대값이 98765 이므로 그냥 98765개짜리 배열에 기입해둬도 된다.)

주의점은 곱의 경우 대략 90000*90000까지 가능해야 하므로, int 범위를 넘어간다. 따라서 long으로 곱한 후 어차피 필요한 최대치는 98765이므로 그 이하라면 int로 변경해서 HashSet에 넣어주면 된다. 합도 마찬가지로 98765 이하의 합만 필요하다. initPnSumAndMult() 를 참고하자. 이 때 곱은 두 소수가 같아도 되지만 합은 같으면 안된다. 이 부분은 if (pn1!=pn2) 로 처리했다.

private void initPnSumAndMult() {
    for (int i = 0; i < pn.size(); i++) {
        for (int j = i; j < pn.size(); j++) {
            int pn1 = pn.get(i);
            int pn2 = pn.get(j);
            long mult = 1l*pn1*pn2;
            if (mult <= LIMIT)
                pnMult.add((int)mult);
            if (pn1!=pn2) {
                int sum = pn1+pn2;
                if (sum <= LIMIT)
                    pnSum.add(sum);
            }
        }
    }
}

 

 

C. 0부터 9까지 K가지의 숫자를 한 번씩 사용해 만들 수 있는 모든 수를 탐색해보자.

  브루트포스 또는 완전탐색의 경우 일반적으로 재귀함수를 사용해 구현하면 편하게 구현할 수 있다. bf(idx, cur)을 참고해보자. idx는 현재 총 몇개의 수를 사용했는지를 나타낸다. idx가 K가 될 경우 K개의 수로 만든 수를 이미 만든 것이므로 base case(기저 사례)가 된다. 재귀 함수에는 항상 base case가 존재해야만 하고, 설정을 세심하게 잘 해줘야 한다. cur은 현재까지 만들어진 수를 뜻한다.

 

  이 때 cur의 경우 매번 기존 값 x 10 후에, 0부터 9까지의 수를 합쳐주면 한 자리씩 숫자를 넣어줄 수 있다(코드의 cur*10+i). 그리고 맨 처음에 '0'은 사용하면 안된다고 했으므로 해당 부분도 체크해주고 (i==0 && idx==0), 각 수가 한번씩만 쓰여야 하므로 방문체크도 해줘야 한다(코드의 v[i]).

private void bf(int idx, int cur) {
    if (idx == k) {
        if (isValid(cur))
            answer++;
        return;
    }
    for (int i = 0; i <= 9; i++) {
        if (i==0 && idx==0 || v[i]) continue;
        v[i] = true;
        bf(idx+1, cur*10+i);
        v[i] = false;
    }
}

 

 

D. 문제에서 제시된 사항들을 만족하는지 확인해보자.

  문제에서 제시한 사항은 서로 다른 두 개의 소수의 합으로 나타낼수 있고, M으로 나누어떨어지지 않을 때 까지 나눈 수가 두 개의 소수의 곱인 경우 이다. 둘 다 만족해야 한다. 'C'에서 기저 사례인 경우에만 확인해주면 된다.

 

  우선 두 소수의 합인지는 'B'에서 미리 계산해둔 HashSet으로 쉽게 알 수 있다. 그럼 M으로 나누어떨어지지 않을 때 까지 나눈 수가 무엇일까? 예를들어 현재 보고 있는 수가 75이고, M=5 라고 해보자. 75는 5로 나누어떨어지므로 나눠주면 15가 된다. 15도 5로 나누어떨어지므로 3이 된다. 3은 5로 나누어떨어지지 않으므로 3이 남고, 이 3이 두 소수의 곱으로 가능한지 확인해주면 된다. 코드로는 while (cur%m==0) cur/=m; 로 이 값을 구해줄 수 있다.

  전체 확인과정은 코드의 isValid()를 참고하자.

private boolean isValid(int cur) {
    if (!pnSum.contains(cur)) return false;
    while (cur%m==0)
        cur/=m;
    if (!pnMult.contains(cur)) return false;
    return true;
}

 

  최종적으로 isValid가 true로 return된 횟수가 답이 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    private static final int LIMIT = 98765;
    ArrayList<Integer> pn = new ArrayList<>();
    HashSet<Integer> pnSum = new HashSet<>();
    HashSet<Integer> pnMult = new HashSet<>();
    boolean[] v = new boolean[10];
    int k, m, answer = 0;

    private void initPn() {
        boolean[] isPn = new boolean[LIMIT+1];
        int sqrtN = (int)Math.sqrt(LIMIT);
        for (int i = 3; i <= sqrtN; i+=2) {
            if (isPn[i]) continue;
            int base = i+i;
            while (base <= LIMIT) {
                isPn[base] = true;
                base+=i;
            }
        }
        pn.add(2);
        for (int i = 3; i <= LIMIT; i+=2) {
            if (!isPn[i]) pn.add(i);
        }
    }

    private void initPnSumAndMult() {
        for (int i = 0; i < pn.size(); i++) {
            for (int j = i; j < pn.size(); j++) {
                int pn1 = pn.get(i);
                int pn2 = pn.get(j);
                long mult = 1l*pn1*pn2;
                if (mult <= LIMIT)
                    pnMult.add((int)mult);
                if (pn1!=pn2) {
                    int sum = pn1+pn2;
                    if (sum <= LIMIT)
                        pnSum.add(sum);
                }
            }
        }
    }

    private boolean isValid(int cur) {
        if (!pnSum.contains(cur)) return false;
        while (cur%m==0)
            cur/=m;
        if (!pnMult.contains(cur)) return false;
        return true;
    }

    private void bf(int idx, int cur) {
        if (idx == k) {
            if (isValid(cur))
                answer++;
            return;
        }
        for (int i = 0; i <= 9; i++) {
            if (i==0 && idx==0 || v[i]) continue;
            v[i] = true;
            bf(idx+1, cur*10+i);
            v[i] = false;
        }
    }

    private void solution() throws Exception {
        initPn();
        initPnSumAndMult();
        pn = null;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        bf(0, 0);
        System.out.println(answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}