공항 문제 링크 각 비행기를 도착하는 순서대로 남은 조건을 만족하는 게이트에 도킹시키는 문제이다. 물론 도킹 수가 최대가 되는 것이 목적이다. 풀이 더보기 게이트의 선택지는 $1\cdots g_i$이다. $g_i$가 큰 비행기들은 굳이 작은 게이트를 택함으로써 $g_i$가 작은 비행기들의 자리를 뺏을 이유가 없다. 따라서 $g_i$ 이하 중 가장 큰 게이트를 택하는 그리디 전략이 성립할 수 있다. 근데... 증명은... 어케하지..? Overplanting 문제 링크 jinhan814님 코드가 깔끔하길래 본계정으로 다시 풀었다. 풀이. 더보기 직사각형의 합집합의 넓이를 구하는 유형인데, $N$이 작다. 그냥 좌표압축 느낌으로 풀이하면 되는데, 구현이 중요하다. 코드 더보기 query, update을 밖으..
밥 먹기 문제 링크 7577번: 탐사의 마이너 버전이라고 할 수 있다. 필자는 '탐사'를 자력으로 못 풀었지만, 어쨌든 '탐사'에 사용되는 방법을 배워서 이 문제를 수월하게 풀 수 있었다. 어쩌면 '밥 먹기'를 푼 뒤 '탐사'를 시도하면 풀 수 있을 것 같기도 하다. 풀이 더보기 상당히 어려운 문제이고, 아이디어성 문제이다. 문제에서 요구하는 것을 간단하게 바꾸면 '연립 부등식의 해를 결정해라' 정도의 얘기가 된다. 완전한 결정을 의미하는 것은 아니지만 아무튼. 신기하게도 떨어지는 거리의 범위가 큰 것이 문제의 힌트가 된다. '탐사'의 경우는 범위가 적어서 오히려 접근이 어려웠다. 따라서 DP의 가능성은 적다. $1\cdots N$을 쭉 나열하고 범위를 표시하면서 파악하면 감을 잡기 쉽다. $D_1$을 ..
계산기하의 기본 도구들을 소개합니다. 마음가짐 기하 문제는 예외 처리가 적고, 구현이 쉬운 형태의 표현 방법 및 풀이를 이용해야 한다. 그리고 실수 좌표보다는 정수 좌표를 이용해야 한다. 그래서 이 글은 실수를 적극적으로 이용하는 문제는 논외로 한다. 그래서 이중적 의미로 "실수 없는 계산기하"이다. 템플릿 기하를 여행하는 Competitive Programmer를 위한 안내서에서 소개된 편리한 표현 방법을 따른다. 위 글에서 참고한 예외 사항이다: 점이 [1, 2개 / 일직선상 / 위에 존재] 직선, 선분이 [평행 / 일직선상] 중복 존재 점과 벡터 complex을 사용한다. Unspecified Behavior임을 감안하여 몇몇 함수들을 재정의한다. Unspecified Behavior임에도 사용하는..
