PS 이야기

코드포스 GYM 링크 B. Colored Blanket 이 문제에서 입력이 어떻게 들어오든 상관 없이 답은 항상 존재한다. 이 사실을 간략하게 보이겠다. 담요가 $k$개 있고, 색상 종류가 최대 $n$개 일 때 아래와 같은 두 조건을 만족한다. 가장 공이 적은 색상의 공의 개수 ≤ $\frac{k}{n}$가장 공이 많은 색상의 공의 개수 ≥ $\frac{k}{n}$ 위 두 조건을 만족하기 때문에 하나의 키트에 가장 공이 적은 색상의 공들을 모두 넣고 남은 빈 공간을 가장 공이 많은 색상의 공으로 채우면 하나의 키트에는 두 색만 존재하여 문제 조건을 만족한다. 그리고 문제는 귀납적이게 한 단계로 줄어든다. 남은 공의 개수는 $k - \frac{k}{n}$개이며, 색상의 종류는 최대 $n-1$개다. #inc..

2차원 좌표계에 모든 변이 x축과 평행하거나 y축에 평행한 직사각형 하나와 선분 하나가 주어졌을 때 교차점의 개수를 구하는 문제다. 이 문제를 편하게 해결하기 위해 두 선분이 주어졌을 때 생기는 교차점의 개수를 세는 함수 intersect(line a, line b)를 생각하자. 두 선분이 서로 다른 직선 성분일 경우, ccw 함수를 이용하여 두 선분이 교차하는지 확인할 수 있다. 만약 교차하면 생기는 교차점의 개수는 1개이며, 교차하지 않는다면 교차점의 개수는 0이다. ccw(point a, point b, point c): (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) 점 a에서 점 b로 갔다가 점 c로 갔을 때 꺽이는 방향이 시계 방향인지 반시계 방향인지 판별하는 함수(..

$1 \times 1$ 크기의 격자 $MN$ 개가 $M \times N$ 크기의 직사각형을 이루고 있다. 각 격자에는 얼룩이 묻어있을 수 있다. $3 \times 3$ 크기의 덮개를 써서 모든 얼룩을 덮고자 할 때, 필요한 덮개의 최소 개수를 구하는 문제다. 이 문제에서 중요한 것은 $M$ 제한이 $N$ 제한에 비해 현저히 작다는 점이다.한 열에 덮개를 배치하는 경우의 수를 생각해보자. 우선 최악의 경우를 고려하기 위해 $M=10$이라 생각하자. 하나의 덮개를 덮개의 가장 윗 행 번호로 표현하자. 같은 행 번호에 여러 덮개가 있으면 항상 비효율적이며, 9번 행과 10번 행으로 표현되는 덮개는 없다. 따라서 $2^8 = 256$가지를 생각할 수 있다. 좀 더 경우의 수를 줄여보자. 10개의 행을 모두 덮는..