백준/수학 (35) 썸네일형 리스트형 백준 14848 - 정수 게임 https://www.acmicpc.net/problem/14848 포함 배제의 원리를 이용해 집합에서 원소들을 지워나가는 문제이다. 단, 이 문제는 서로 배수 관계인 수가 있을 수 있으므로 원소들을 곱할 때 최소공배수를 계산해야 올바른 답을 얻을 수 있다. 전체 코드 더보기 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma") .. 백준 2381 - 최대 거리 https://www.acmicpc.net/problem/2381 서론 이 문제에서 써야 하는 테크닉은 은근 Well-Known이라고 한다. 대회를 준비하는 사람이라면 한 번쯤 익혀둘 필요가 있다. 식 전개 서로 다른 두 점의 좌표를 각각 $(x_{i}, y_{i}), (x_{j}, y_{j})$라고 하자. 그러면 두 점의 맨해튼 거리는 $|x_{i} - x_{j}| + |y_{i} - y_{j}|$임은 너무나도 잘 알고 있다. 자 여기서 신기한 걸 해보자. 우리는 $max(|x_{i} - x_{j}| + |y_{i} - y_{j}|)$를 구할 건데 절댓값을 어떻게 없앨까? 절댓값을 없애기 위해 다음과 같은 전개가 가능하다. $max(|x_{i} - x_{j}| + |y_{i} + y_{j}|) = ma.. 백준 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 힌트 더보기 수열의 길이는 무한으로 둔다. 풀이 풀이는 기술하지 않는다. 제출 기록 이전 1 2 3 4 5 6 7 다음
