본문 바로가기

백준_BOJ/BOJ (플래티넘)

(2)
[백준/알고리즘] 17941번 목장 CCTV (플래티넘 5) BOJ 17941번 풀이 알고리즘 : 세그먼트 트리, 슬라이딩 윈도우 2020년도 UCPC를 연습할 겸 풀어본 대회(HCPC)에 있는 문제입니다. 문제를 간단히 다시 설명하면, N x M 크기의 목장에 양들이 있고, 양들은 크기가 정해져 있습니다. 그 목장에 CCTV를 설치하는데 CCTV는 아래로 r, 오른쪽으로 c만큼 크기의 직사각형을 촬영합니다. 특이하게, 이 CCTV는 촬영한 범위 내의 가장 큰 양의 크기를 알려줍니다. 그리고 방향을 나타내는 정수 D가 주어지는데, 이는 모든 양들이 상/하/좌/우 중 입력된 한 방향으로 하루에 한칸씩 이동합니다. 그래서 문제에서는 K일 동안 촬영했을 때, 각 촬영마다 촬영한 가장 큰 양의 크기를 모두 XOR한 값을 출력하는게 목표입니다. 이때 주의해야 할 점은, 문..
[백준/알고리즘] 8986번 전봇대 (플래티넘 5) BOJ 8986번 현재 전봇대의 위치가 X축 위에 좌표로 나타내져 있다. (첫번째 전봇대는 항상 0에 위치한다.) 이 전봇대들을 일부 움직여서, 서로 이웃한 전봇대 사이의 거리를 일정하도록 옮기려고 한다. 이때, 이웃한 전봇대 사이의 거리를 일정하도록 하는 이동거리의 합의 최솟값을 출력하시오. 풀이 알고리즘 : 이분탐색, 삼분탐색 지금 풀고있는 백준 문제집의 마지막 문제여서 처음보는 삼분탐색 알고리즘도 공부하고, 겨우겨우 풀게 되었다. 초기 전봇대의 좌표를 d0, d1, d2, ..., d(n - 1)이라고 하자. 이웃된 전봇대의 거리를 일정하게 x로 맞춘다고 가정하면, 이때의 좌표는 0, 1 * x, 2 * x, ..., (n - 1) * x로 표현이 가능하다. 이때, 이동거리함수 f(x)는 다음과 같..