더 이상 물러설 곳이 없다

www.acmicpc.net/problem/2004

문제

(nm)의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.

출력

첫째 줄에 (nm)의 끝자리 0의 개수를 출력한다.

예제 입력 1

25 12

예제 출력 1

2

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // nCm = n! / (m! * (n-m)!)
        // m!, (n-m)!은 분모에 들어가기 때문에 역으로 뺴줘야 한다

        int cntOfTwo = 0, cntOfFive = 0;
        for(long i = 2; i <= n; i*=2) cntOfTwo += n / i;
        for(long i = 2; i <= m; i*=2) cntOfTwo -= m / i;
        for(long i = 2; i <= n-m; i*=2) cntOfTwo -= (n-m) / i;

        for(long i = 5; i <= n; i*=5) cntOfFive += n / i;
        for(long i = 5; i <= m; i*=5) cntOfFive -= m / i;
        for(long i = 5; i <= n-m; i*=5) cntOfFive -= (n-m) / i;

        int ans = Math.min(cntOfTwo, cntOfFive);
        System.out.println(ans);
    }
}

codeung.tistory.com/170 와 유사한 문제이다.

다만 이 문제에서는 5의 개수로 (2 * 5) 쌍의 개수를 퉁칠 수 없다.

nCm = n! / (m! * (n-m)!) 인데, n!을 m! * (n-m)! 으로 나눌 때 변수가 생길 수 있기 때문에 온전히 nCm 안에 있는 (2 * 5) 쌍의 개수를 전부 구해야 한다.

(분모에 위치한 m!, (n-m)! 에 대해서는 나온만큼 n!에서 나온 개수에서 빼주면 된다.)

주의할 점은 각 반복의 변수 i 를 int가 아닌 long으로 써야 한다는 것이다.

n, m의 상한은 20억으로 int의 범위 안에서 충분히 처리가 가능하긴 하지만.. 반복변수 i는 1씩 증가하는 것이 아니라 2배, 5배씩 증가하기 때문에 n과 int 범위 안에서 잘 있다가 갑자기 int 범위를 벗어나게 될 수 있기 때문이다.

실제로 int i 를 사용할 경우 0 divide exception이 발생하게 된다.

www.acmicpc.net/problem/1676

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

예제 입력 1 복사

10

예제 출력 1 복사

2

예제 입력 2 복사

3

예제 출력 2 복사

0

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int cntOfFive = 0;
        cntOfFive += n / 5;
        cntOfFive += n / 25;
        cntOfFive += n / 125;

        System.out.println(cntOfFive);
    }
}

n을 소인수분해 했을 때 10이 즉, 뒤에 0이 붙을 수 있는 경우는 (2 * 5) 쌍이 나올 때 뿐이다.

즉, n을 소인수분해 하여 (2*5) 꼴이 몇 개 나오는지를 알아내면 된다.

그런데 2는 짝수가 나올 때마다 하나씩 추가되기 때문에 무조건 5보다 많이 나올 수밖에 없다.

따라서 n 안에 5의 배수가 몇 번이나 들어있는지를 구하면 그게 곧 (2 * 5) 쌍의 개수이다.

여기서 주의할 점은, 25, 125 등의 수는 5의 배수가 맞긴 하지만 5가 하나만 들어있는 게 아니다

(25 = 5 * 5, 125 = 5 * 5 * 5 ... )

즉, 5의 배수의 개수를 구한 다음 25의 배수의 개수를 구해서 25 = 5 * 5 에서 남아있는 5를 한 번 더 세어줘야 한다.

(125는 5 * 5* 5 이므로 5가 한 번 더 들어가니깍 125의 배수의 개수도 구해야 한다.)

n의 제한범위 500 안에서 5의 지수승 꼴은 최대 5^3 = 125 까지만 등장하기 때문에 125의 배수의 개수까지만 구해주면 된다.

www.acmicpc.net/problem/10872

문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(0 ≤ N ≤ 12)가 주어진다.

출력

첫째 줄에 N!을 출력한다.

예제 입력 1 복사

10

예제 출력 1 복사

3628800

예제 입력 2 복사

0

예제 출력 2 복사

1

풀이 .

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int factorial = 1;
        for(int i = 1; i <= n; i++) {
            factorial *= i;
        }
        System.out.println(factorial);
    }
}

www.acmicpc.net/problem/11653

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

예제 입력 1

72

예제 출력 1

2

2

2

3

3

예제 입력 2

3

예제 출력 2

3

예제 입력 3

6

예제 출력 3

2

3

예제 입력 4

2

예제 출력 4

2

예제 입력 5

9991

예제 출력 5

97

103

풀이 .

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        if(n == 1) return;
        while(n != 1) {
            for(int i = 2; i <= n; i++) {
                if(n % i == 0) {
                    n /= i;
                    sb.append(i + "\n");
                    break;
                }
            }
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

그냥 소인수분해 하면 된다.

www.acmicpc.net/problem/6588

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

예제 입력 1

8

20

42

0

예제 출력 1

8 = 3 + 5

20 = 3 + 17

42 = 5 + 37

풀이 .

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // get prime (sieve of eratosthenes)
        int[] prime = new int[1000001];
        boolean[] isNotPrime = new boolean[1000001];
        int cntOfPrime = 0;
        for(int i = 2; i <= 1000000; i++) {
            if(isNotPrime[i] == false) {
                prime[cntOfPrime++] = i;
                for(int j = i + i; j <= 1000000; j+=i) {
                    isNotPrime[j] = true;
                }
            }
        }

        String input = null;
        while(!(input = br.readLine()).equals("0")) {
            int n = Integer.parseInt(input);
            for(int i = 1; i <= cntOfPrime; i++) {
                if(isNotPrime[n - prime[i]] == false) {
                    sb.append(n + " = " + prime[i] + " + " + (n - prime[i]) + "\n");
                    break;
                }
            }
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

1. 에라토스테네스의 체를 사용해 MAX 범위 내의 소수들의 배열을 미리 구해놓는다.

2. n - prime[i]이 소수인지를 작은 소수부터 비교한다.

3. b - a가 최대인 a, b 라는 조건을 맞추기 위해 2번에서 작은 소수부터 검사한 것. 정답 찾으면 바로 break하여 다음 테스트 케이스 수행

(골드바흐의 추측은 10^18 이하까지는 참인 것이 증명되었으므로 실패 경우에 대한 고려는 하지 않는다.)

www.acmicpc.net/problem/1929

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

3

5

7

11

13

풀이 .

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static boolean isPrime(int num) {
        if(num == 2) return true;
        if(num == 0 || num == 1 || num % 2 == 0) return false;
        for(int i = 3; i <= Math.sqrt(num); i+=2) {
            if(num % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        for(int i = m; i <= n; i++) {
            if(isPrime(i)) sb.append(i + "\n");
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

www.acmicpc.net/problem/1978

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1

4

1 3 5 7

예제 출력 1

3

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static boolean isPrime(int num) {
        if(num == 2) return true;
        if(num == 0 || num == 1 || num % 2 == 0) return false;
        for(int i = 3; i <= Math.sqrt(num); i+=2) {
            if(num % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(isPrime(num)) cnt += 1;
        }
        System.out.println(cnt);
    }
}

www.acmicpc.net/problem/11576

문제

타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 세계에서도 프로그래밍을 하고 싶었던 정이는 백준 사이트에 접속하여 문제를 풀기로 하였다. 그러나 미래세계는 A진법을 사용하고 있었고, B진법을 사용하던 정이는 문제를 풀 수가 없었다. 뛰어난 프로그래머였던 정이는 A진법으로 나타낸 숫자를 B진법으로 변환시켜주는 프로그램을 작성하기로 하였다. 

N진법이란, 한 자리에서 숫자를 표현할 때 쓸 수 있는 숫자의 가짓수가 N이라는 뜻이다. 예를 들어 N은 17일 때 한 자릿수에서 사용할 수 있는 수는 0, 1, 2, ... , 16으로 총 17가지가 된다.

입력

입력의 첫 줄에는 미래세계에서 사용하는 진법 A와 정이가 사용하는 진법 B가 공백을 구분으로 주어진다. A와 B는 모두 2이상 30이하의 자연수다.

입력의 두 번째 줄에는 A진법으로 나타낸 숫자의 자리수의 개수 m(1 ≤ m ≤ 25)이 주어진다. 세 번째 줄에는 A진법을 이루고 있는 숫자 m개가 공백을 구분으로 높은 자릿수부터 차례대로 주어진다. 각 숫자는 0이상 A미만임이 보장된다. 또한 수가 0으로 시작하는 경우는 존재하지 않는다.

A진법으로 나타낸 수를 10진법으로 변환하였을 때의 값은 양의 정수이며 220보다 작다.

출력

입력으로 주어진 A진법으로 나타낸 수를 B진법으로 변환하여 출력한다.

예제 입력 1

17 8

2

2 16

예제 출력 1

6 2

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(br.readLine());

        int[] aArr = new int[m];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            aArr[i] = Integer.parseInt(st.nextToken());
        }

        int idx = 0, decimal = 0;
        for(int i = m - 1; i >= 0; i--) {
            decimal += aArr[idx++] * Math.pow(a, i);
        }

        int[] bArr = new int[20];  // decimal은 2^20 미만으로 보장됨
        idx = 0;
        while(decimal != 0) {
            bArr[idx++] = decimal % b;
            decimal /= b;
        }

        for(int i = idx - 1; i >= 0; i--) {
            System.out.print(bArr[i] + " ");
        }
    }
}