백준/수학 (28) 썸네일형 리스트형 백준 15965 - K번째 소수 필요 지식 이 문제는 소수 정리를 알면 매우 단순해진다. 풀이 소수 정리에 의해 ${e^{16} \over 16} \approx 555381$를 계산할 수 있고 $e^{16}$ 정도의 범위는 에라토스테네스의 체로 충분히 계산할 수 있음을 알 수 있다. 체를 돌려 50만번째 소수까지 찾아 출력하도록 하면 된다. 전체 코드 - 여기서는 linear sieve를 사용했다. 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma") #pragma.. 백준 16878 - 궁전 https://www.acmicpc.net/problem/16878 대부분의 평범한 컴퓨터 공학 학부생은 풀 수 없는 문제로 보인다. 이 문제는 Hertzsprung's problem라는 이름으로 알려져 있으며 원본 문제는 각 열과 행에 킹이 하나만 있게 하면서 서로를 공격할 수 없게 배치하는 경우의 수를 구하는 것이다. 다행히도 OEIS에는 제한 시간 안에 충분히 돌아가는 단순한 점화식을 제공하는데 다음과 같다. $dp(0) = dp(1) = 1$ $dp(2) = dp(3) = 0$ $dp(4) = 2$ $dp(n) = (n + 1)dp(n - 1) - (n - 2)dp(n - 2) - (n - 5)dp(n - 3) + (n - 3)dp(n - 4) (n \geq 5)$ 이 점화식으로 동적 계획법을 짜.. 백준 1402 - 아무래도이문제는A번난이도인것같다 https://www.acmicpc.net/problem/1402 힌트 더보기 수열의 길이는 무한으로 둔다. 풀이 풀이는 기술하지 않는다. 제출 기록 백준 16563 - 어려운 소인수분해 https://www.acmicpc.net/problem/16563 소인수 분해는 $O(\sqrt N)$의 시간 복잡도로 $\sqrt N$까지 반복문을 돌아 자연수를 나누는 방법이 가장 잘 알려져 있다. 하지만 이 문제는 소인수 분해를 해야 할 수의 개수가 $N \leq 10^{6}$이므로 이 방법을 사용하면 TLE 판정을 받게 된다. Linear sieve를 이용하여 소인수 분해를 $O(\log N)$에 할 수 있는 방법이 있다. Linear sieve를 사용하여 소수 목록을 $O(N)$에 구한 후 소인수 분해를 실시하면 1초 이하의 시간으로 AC를 받을 수 있다. Linear sieve를 알지 못한다면 이 글을 참조하여 사용하면 된다. 백준 10728 - XOR삼형제 1 https://www.acmicpc.net/problem/10728 대회 에디토리얼에 의하면 이 문제는 백트래킹 사용을 염두에 두고 나온 것으로 보인다. 다만 백트래킹으로 문제를 푸는 것은 그다지 의미가 없다고 판단되어 제한이 더 큰 XOR삼형제 2에도 쓸 수 있는 솔루션을 동일하게 적용했다. 여기에서 확인할 수 있다. 이전 1 2 3 4 5 6 다음
