이번 문제는 조합과 조합의 수에 대해 알아야 온전히 이해하고 풀 수 있다고 생각한다. 혹시, 조합식은 알지만 소인수분해에 관해 어려움을 겪고 있다면 이 문제를 풀기보다 아래의 문제를 풀어보고 이 문제를 푼다면 정말 쉽게 풀 수 있을 것이다. https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 먼저 nCm이란 조합식이다. 정의는 서로 다른 n개의 원소 중, 순서를 가리지 않고 m개의 원소를 선택하는 것을 말한다. 그럼 이 조합식을 어떻게 구할 수 있을까? 조합식의 공식을 이용하자 수학 블로그는 아니기 때문에 공식만 공유하고 넘어가겠다...
이번 문제는 N!이 뒤에 몇개의 0이 있는지 구하면 된다. 우선 0을 만들기 위해선 당연히 2와 5의 곱으로 이루어져야 한다. 이외의 경우엔 절대 없다. 따라서 이 문제를 해결하기 위해선, 2와 5의 지수를 구하고, 더 작은 값이 0의 개수가 될 것이다. 그럼 어떻게 소인수분해를 하는 것이 좋을까? 팩토리얼을 진짜 계산해버리는거? 나눗셈? 우선 10! 팩토리얼도 내가 알기로 300만? 정도 되는걸로 알고 있다. 이건 너무 아닌거 같은 방법이다. 나는 이렇게 소인수 분해를 하였다. 예를 들어, 30까지의 수가 있을 때 5의 지수의 개수는 다음과 같이 구할 수 있다. 1. 5의 배수의 개수를 구한다. (파란색) : 6개 2. 5^2의 배수의 개수를 구한다(주황색) : 1개 1 2 3 4 5 6 7 8 9 1..
이번 문제는 골드바흐의 추측 문제를 풀고 오는 길이라 매우 간단하게 해결할 수 있었다. 나는 먼저 100만까지 모든 소수를 먼저 구하고, 파티션의 개수를 구하는 방식으로 구현하였다. 아래는 에라토스테네스의 체를 이용하여 소수를 구하는 가장 흔하면서 간단한 코드이다. int max = 1_000_000; int[] prime = new int[max]; boolean[] check = new boolean[max+1]; int k = 0; for(int i = 2; i
이번 문제는 수학적 지식이 어느정도 요구하는 문제라고 생각한다. 우선 이 문제를 0.5초 안에 구하려면 에라토스테네스의 체와 같은 효율적인 알고리즘을 알고 있어야 한다고 생각한다. 무식하게(?) 순회로는 절대 풀수 없다. 또한 나는 이 문제를 풀면서 최대한 시간 복잡도를 지키면서 구현했는데 몇번 시간초과가 났다. 그런데 에라토스테네스의 체를 이용하여 구현했으므로 로직이 느려서 그런건 아닌 거 같아서 이때까지 계속 출력할 때 써왔던 StringBuilder 대신, 자바에선 가장 빠룬 BufferedWriter로 출력하니 시간초과 없이 통과가 됐었는데 약간 어이가 없었다.. 일단 나는 이 문제를 에라토스테네스의 체를 구하는 부분과 골드바흐의 추측을 구하는 부분으로 총 2부분으로 나누어 간단히 설명하겠다. 아..
이번 문제는 에라토네스의 체를 이용하여 문제를 풀어보겠다. 먼저, 에라토네스의 체를 이용하면 효율적이게 소수가 아닌 수들을 구해낼 수 있다. 자세한 에라토네스의 체는 검색하길 바라며, 나는 아래와 같이 구현했다. 소수가 아닌 수를 구할 때, set에 저장하여 소수가 아닌 수를 구하고, 소수인 수를 구할 땐 set에 포함된 수인지 확인하는 방식으로 하였다. import java.util.*; public class M1929 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int M = sc.nextInt(), N = sc.nextInt(); StringBuilder sb = new StringBuilder();..
이번 문제는 매우 간단하다. 우선 나는 소수를 구하기 위해서 가장 먼저 생각한 방법은 순회하며 나머지가 0이 나온다면 소수가 아닌 방식으로 판단하는거였다. 이번 문제는 제한 시간이 충분히 주어져서 문제를 푸는덴 솔직히 상관은 없지만 뭔가 내키지 않은 방식이란걸 여러분도 느꼈을 것이다. 우선 소수란, 다들 알겠지만 약수로 1과 자신만을 가지는 수이다. 따라서 그 수는 이들 이외의 수를 약수로 가지면, 소수가 아닌 것이다. 이 특징을 이용하면 되는데, 예를 들어 수가 10인 경우, 굳이 2~10 전체를 나눠가면서 나머지를 구할 필요없이, 올 수 있는 약수의 범위인 2~5만 나누면 되지 않을까? 왜냐하면 해당 수가 가질 수 있는 최대 약수의 범위는 (수/2)이기 때문이다. 그 특징을 이용하면 조금은 더 효율적..
이 문제는 내가 작성한 최소 공배수와 최대 공약수 문제 풀이를 읽었다면 그냥 똑같기 때문에 매우 쉽게 구현할 수 있다. 워낙 쉬운 문제이기에, 따로 설명은 안하지만 의외로 시간초과가 많았던 거 같다. 이 문제를 풀 때, 혹시나 순회하면서 나머지를 구하는 방식은 잘못하면 시간 초과가 날 수 있다는 것을 유념하면 된다. 이전에도 말했던 유클리드 호재법을 이용해서 풀면 너무나 쉽기 때문에 한번 보는 걸 추천한다. import java.io.*; import java.util.StringTokenizer; public class M1934 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe..
이번 문제는 효율적인 알고리즘으로 푸는 법도 소개하겠다. num1, num2의 최소공배수는 grtDivisor, 최대 공약수는 lstMultiple이라고 하겠다. 우선 간단히, 최소 공배수를 구할 때, 많이들 몫중 가장 큰 값을 반복문으로 순회하면서 구하지 않을까 싶다. 또한 최대 공약수는 "(num1 * num2) / grtDivisor"로 구할 수 있다. import java.util.*; public class S2609 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num1 = sc.nextInt(), num2 = sc.nextInt(); int max = Math.max(num1, num2);..
정말 쉬운 문제이므로, 설명은 생략하겠다. import java.io.*; public class M3052 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); boolean[] diff = new boolean[42]; int count = 0; for(int i = 0; i < 10; i++) diff[Integer.parseInt(br.readLine()) % 42] = true; for(boolean yes : diff) { if (yes) count++; } System.out.println(count); ..
