백준 (223) 썸네일형 리스트형 백준 1657 - 두부장수 장홍준 https://www.acmicpc.net/problem/1657 현재 위치에서 뒤의 몇 열을 비트 마스크로 관리하는 dp이다. 풀이의 근원은 이 포스트, 또는 이 자료를 참조하라. 이 문제는 위와 달리 칸을 선택하지 않는 경우도 있으므로 이를 고려해서 동적 계획법을 수행하면 된다. 전체 코드 더보기 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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 8.. [KOI] 백준 10937 - 두부 모판 자르기 https://www.acmicpc.net/problem/10937 현재 위치에서 뒤의 몇 열을 비트 마스크로 관리하는 dp이다. 풀이의 근원은 이 포스트, 또는 이 자료를 참조하라. 이 문제는 위와 달리 칸을 선택하지 않는 경우도 있으므로 이를 고려해서 동적 계획법을 수행하면 된다. 전체 코드 더보기 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 65 66 67 68 69 70 71 72 73 74 75 #pragma GCC .. [KOI] 백준 2673 - 교차하지 않는 원의 현들의 최대집합 https://www.acmicpc.net/problem/2673 관찰 주어진 그림을 보자. 5~27을 무조건 연결한다고 가정하면 구간 [5, 27] 내의 점과 교차하는 현을 잇는 것은 불가능하다. 하지만 해당 구간을 벗어나는 현과는 연결할 수 있다. 다시 말해 어떤 현의 두 점이 구간 밖에 있으면 교차하지 않게 선택할 수 있다는 것이다. 아래의 그림처럼 어떤 현을 기준으로 했을 때 그 구간보다 작은 현들을 최대한 선택해야 함을 이해할 수 있다. 즉, 작은 구간에서 교차하지 않은 현의 최대 개수에서 큰 구간에서 교차하지 않는 현의 최대 개수로 누적하는 동적 계획법으로 생각할 수 있다. 헷갈리는 경우 만약 100과 1이 연결되어 있다고 해보자. 100~1의 길이는 작지만 구간으로 표현하면 [1, 100]으.. [KOI] 백준 2502 - 떡 먹는 호랑이 https://www.acmicpc.net/problem/2502 힌트 더보기 첫날에 준 떡의 양을 $f_{1}$, 둘째 날에 준 떡의 양을 $f_{2}$라고 하자. 떡을 주는 규칙을 살펴보면 $f_{n} = f_{n - 1} + f_{n - 2}$으로 피보나치 수열과 같은 점화식이다. 조건을 만족하는 적절한 $f_{1}$과 $f_{2}$는 $O(DK \log K)$의 시간복잡도로 찾을 수 있다. $f_{1}$가 정해져 있을 때 $f_{2}$를 찾는 방법을 생각한다. 풀이 더보기 선형 점화식 $f_{n} = f_{n - 1} + f_{n - 2}$로 계산한 $f_{d}$가 주어질 때 $f_{1}$과 $f_{2}$를 구하는 문제이다. 각 항에 대해 값을 1부터 $10^{5}$까지 무식하게 찾으면 시간복잡도.. 백준 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.. 이전 1 ··· 9 10 11 12 13 14 15 ··· 45 다음
