PS/Search(2)
-
BOJ 1637 : 날카로운 눈
https://www.acmicpc.net/problem/1637 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 아주 재밌는 문제이다. 보기 전에 꼭 혼자서 시도해보고 오길 바란다. f(n) = n 이하의 수들의 갯수 라고 한다면 f(n)이 최초로 홀수가 되는 순간이 답일 것이다. f(n)이 최초로 홀수가 되는 순간을 이분탐색으로 찾으면 된다. 코드
2021.08.03 -
BOJ 15976 : XCorr
www.acmicpc.net/problem/15976 15976번: XCorr $ 1 \le N, M \le 3,000, 1 \le n \le 3,000, -3,000 \le a \le b \le 3,000$ 이다. www.acmicpc.net 처음에는 어려웠는데, 생각해보니 진짜 쉬운 문제였다. 그냥 x_i를 기준으로 해서 범위 안의 y_i를 모두 더한다. 이는 Prefix-Sum을 활용하고, a_i값에 알맞게 범위를 찾아주는 것은 이분 탐색을 활용하거나 표준 라이브러리를 이용한 lower_bound, upper_bound를 이용한다. #include #define MEM 300005 #define sanic ios_base::sync_with_stdio(0) using namespace std; ty..
2020.09.09