https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 도토리가 들어간 상자번호를 구해내는 문제. 간격을 d로 두며, 구간 [a,b] 에서 도토리가 들어가있는 상자의 개수는 min(b,now)/d - a/d +1이다. now 는 내가 정한 상자번호. /d 로 묶어보면 좀 더 자명해지는데, (min(b,now) - a)/d + 1로, b보다 now가 더 작으면 세면 안..
https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제에서 제시한 B[K] 가 K번째로 큰 수 이니까 K를 다르게 해석해보자면 B[K] 보다 작거나 같은 수가 K개 있는 것이 된다. 그래서 B[K]를 mid로 잡고 파라메트릭 서치하면서 개수만 세주면 K에 대한 답을 구할 수 있다. B[K] 가 mid로 잡힌거기때문에 파라메트릭 구간의 끝값이 N*N 인줄 알았는데 AC코드까보니까 K도 된다고하는데 왜인지는 모르겠다. ..
아니 이거 왤케 역겨움;; https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net Hmaxhp 를 파라메트릭 서치해주면 된다. 숫자 범위부터 해서 상당히 역겨운 문제인데 몇가지 들어보자면 1. 나이브하게 싸우는걸 시뮬레이션하면 TLE를 받음 2. 파라메트릭 최고범위가 123456 * 1e12 Hmaxhp ll mid = (s+e)/2; if(s>e) return s; ll Hmaxh..
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 처음 보고 뇌절이 심하게 왔었는데, 지문에서 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 를 보고 저 "가장 인접한 두 공유기 사이의 거리" 가 파라메트릭으로 얻고자 하는 값일거라는 킹리적 갓심을 하고 짜서 AC받았다. 가장 인접한 두 공유기 사이의 거리는 아무리 길어도 (오른쪽끝 - 왼쪽끝) 의 길이보다 길 수 없다..
파라메트릭 서치는 몇번을 해도 ㄹㅇ 이 뇌절을 막을수가 없음 어떻게하는지 아직도 잘 ㅁㄹ겠다. https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 블루레이의 녹화 가능한 길이에 따라서 True/False 여부가 갈리는 이분탐색 문제였다. M개로 쪼개는건 그냥 나이브하게 O(N) 에 처리가능. 파라메트릭이 상수가 많이붙어서그렇지 O(log1e9) 상수시간에 처리가 되고있는데 TLE를 받진 않을거같다. 더보기 #include using namespace st..
통신교육 문제 겸 백준에도 있길래 날먹했다 나이스 단순한 이진탐색인데 맞왜틀을 왜이렇게 많이 했는지 모르겠고 AC받긴 했지만 솔직히 WA코드랑 뭔차인지도 잘 모르겠지만 proofed by AC기법으로 증명되었기에 여기다 써본다. www.acmicpc.net/problem/19845 19845번: 넴모넴모 2020 오래된 테트리스 게임판 위에 수수께끼의 생물 “넴모”들이 살기 시작했다. 이 게임판은 가로로 109칸, 세로로 N층 크기이고, 넴모 한 마리는 한 층의 한 칸을 차지하고 산다. 편의상 왼쪽에서부 www.acmicpc.net search 함수는 전형적인 이분탐색 함수이다. 그냥 적당히 짰다. nemo는 혹시몰라 엄청 넉넉하게 만들어뒀는데 솔직히 필요없을거같다 #include #include usi..