Algorithm [Math] 코딩 테스트에서 나오는 수학 개념 정리2

목차

1. 30의 배수 :  백준 [10610] 30   

2. 크기가 매우 커지는 곱하기 : 백준 [1456] 거의 소수 

30의 배수 

관련 문제 : 백준 [10610] 30   https://www.acmicpc.net/problem/10610

 

문제 설명 

숫자가 주어지고 포함된 숫자를 섞어서 30의 배수가 되는 가장 큰 수를 만들고 싶다. 

ex) 102                    210

ex)  80875542         88755420

 

N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

입력 크기가 long으로 담지 못할 만큼 큰 숫자이다.

 

어떻게 해결할까?

먼저 30의 배수가 되는 조건을 생각해 보자.

 

30은 3과 10의 LCM 이다. 

 

1. 숫자의 각 자릿수 합이 3의 배수이면 그 수는 3의 배수이다. (숫자를 섞는다고 해서 각 자릿수의 합이 변하는 경우는 없다.)

 

2. 1번 조건은 주어진 숫자에서 확인하면 되는 조건이고 그럼 나머지 조건은 10의 배수이다. 10의 배수는 그냥 제일 끝자리 숫자가 0이면 10의 배수이다. 

 

문제 해결 방법

1. 각 자릿수 합이 3의 배수인지 확인 3의 배수가 아니면 return -1 

2. 주어진 숫자에 0이 있는지 확인한다. 0이 1개도 없으면 return -1

3. 1번 2번 조건을 통과하면 가지고 있는 숫자들로 제일 큰 숫자를 만든다. (물론 마지막 숫자는 0) 

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       String input = br.readLine();
        int [] memo = new int[10];
        int size = input.length();
        long sum = 0;
        for (int i = 0; i < size; i++) {
            int cur = input.charAt(i) - '0';
            sum += cur;  
            memo[cur]++;
        }
        if(sum % 3 != 0 || memo[0] <= 0){
            System.out.println(-1);
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 9; i >=0 ; i--) {
            while (memo[i] > 0){
                sb.append(i);
                memo[i]--;
            }
        }
        System.out.println(sb);
    }
}

 

크기가 매우 커지는 곱하기

관련 문제 : 백준 [1456] 거의 소수 https://www.acmicpc.net/problem/1456 

 

문제 설명

어떤 수가 소수의 N제곱(N>=2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

 

EX) 예제 입력 2

1 10

 

answer : 3  [2^2 = 4, 2^3 = 8 , 3^2 = 9]

 

문제 제한 ( 1 <= A <= B <= 10^14)

 

문제에서 제일 크게 입력되는 B의 값은 10^14이다. 

 

B 보다 작으면서 N제곱 꼴이려면 비교해 봐야 하는 대상은 최대 √B 이다. 

에라토스테네스의 체를 활용해서 풀어보자.

 

에라토스테네스 체[boolean 배열 초기화] 

static final int INF = 10000000;
boolean [] visited = new boolean[INF+1];

 

기본적인 에라토스테네스 체를 구현한 for문과 동일하다. 

 for(int i = 2; (long)i * i <= b; i++){
      if(visited[i]) continue;
      for (int j = 2; j * i <= INF; j++) {
           visited[j * i] = true;
      }
 }

 

이제 핵심 로직 이번 소수(2,3,5,7,11......) 의 N제곱 꼴인 숫자 개수 확인하기 

long cur = i;
while (cur <= b / i){
    cur *= i;
    if(a <= cur) cnt++;
}

 

처음 문제를 풀 때는 cur * i <= b 이렇게 조건을 확인했다.

하지만 이렇게 하면  overflow가 발생하면서 cur 이 음수로 바뀌어서 잘못된 데이터가 while문 안에서 돌게 되었다. 

cur * i <= b 의 조건식은 cur <= b / i 와 동일하다 (진짜 꿀팁!)
cur이 a보다 크거나 같다면 cnt를 증가시켜준다.

 

최종 코드 

import java.io.*;
import java.util.*;
public class Main {
    static final int INF = 10000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        boolean [] visited = new boolean[INF+1];

        int cnt =0;

        for (int i = 2; (long)i * i <= b; i++) {
            if(visited[i]) continue;
            for (int j = 2; j * i <= INF; j++) {
                visited[j * i] = true;
            }
            long cur = i;
            while (cur <= b / i){
                cur *= i;
                if(a <= cur) cnt++;
            }
        }
        System.out.println(cnt);
    }
}