전체 글 썸네일형 리스트형 BOJ)5846 Tractor 문제: icpc.me/5846 n^2의 격자에서 한 점에서 4방향으로 일정 조건(둘의 차이가 k이하이면 이동 가능)을 만족하면 이동가능할 때임의의 한점을 잡아 반 이상의 격자를 순회할 수 있는 최소의 k를 찾는 문제이다. 최대중의 최소를 구하는 문제이므로 파라메트릭 서치를 생각해볼 수 있다.이 때 k를 mid값으로 정해놓은 뒤에 만족 여부를 확인하게 되는데만족여부는 dfs를 통하여 확인할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace std;int n, a[555][555], b[555][555];int dx[] = .. 더보기 BOJ)5849 Cow Crossings 문제: icpc.me/5849N개의 2점이 주어진다.a[i]와 b[i]인데 이 문제는 각 (a[i],0)과 (b[i],1) 두 점을 잇는 N가지 직선들 중 다른 어떤 직선과도 겹치지 않는 직선의 수를 세는 문제이다.N^2으로 완전 탐색을 하는 방법으로는 해결이 불가능하니, 보통 이러한 류의 문제에서는 스위핑을 이용하게 되는데우선 a[i]를 기준으로 정렬을 해보자.그러고 a[i]가 증가하는 순서대로 보면 이러한 생각을 하게 될 수 있다.내가 이전에 본 직선들의 b[x]의 좌표 중에 나의 b[i]보다 하나라도 큰 수가 있다면 나는 이전에 업데이트 된 직선에 의해서 겹치는 직선이 된다는 걸 알 수 있다.이러한 원리로 우선 a[i]가 증가되는 순서로 안되는 직선들을 걸러준다.하지만 이렇게 처리하면 몇가지 직선이.. 더보기 제이크 USB 11번가 이벤트로 100원에 구매하였다.귀엽다. 더보기 이전 1 ··· 8 9 10 11 12 13 14 ··· 118 다음
