PS 이야기

온라인 아카이브 링크 A. The Mountain of Gold? 0번 도시에서 시작하고 시공간을 이동할 수 있는 수단들이 주어졌을 때, 0번 도시의 과거로 돌아올 수 있는지 판별하는 문제다. 일반적으로 $O(NM)$ 시간복잡도의 Bellman-ford 알고리즘은 전체 그래프에서 음수 싸이클이 있는지 판별할 때 쓰인다. 이 문제에서는 0번 도시와 강하게 연결된 연결 요소(0번 도시에서 $x$로 갈 수 있고, $x$에서 0번 도시로 올 수도 있는 $x$들의 집합)에서 음수 싸이클이 있는지 Bellman-ford로 $O(NM)$만에 확인해주면 된다. #include #include #include using namespace std; typedef vector arr; int T, N, M; int D[10..

Grundy Number는 게임 문제에서 많이 사용되는 방법 중 하나다. Grundy Number는 게임 상황을 Nim Game으로 변환 시켜주는 과정이라고 볼 수 있다. 어떤 상황 $S$에 대한 Grundy Number를 구하는 방법은 아래와 같다. 상황 $S$에서 다음 상황들 중 하나를 $S'$라고 하자. $G(S) = \min(v) $ ($v \not\in \{G(S')\}$) 즉, 상황 $S$의 Grundy Number $G(S)$는 상황 $S$의 다음 상황들 $S'$의 Grundy Number $G(S')$들 중 존재하지 않는 가장 작은 수다. 각 상황들을 Grundy Number로 표현했을 때, 필승법의 여부는 Nim Game과 마찬가지로 구하면 된다. Grundy Number로 표현된 각 상..

온라인 아카이브 링크 A. Number Assignment 문제에서 주어진 수들을 정렬한 다음 Dynamic Programming를 이용해 해결한다. D[i][j] = 1~i번 수가 있고, 이를 j개의 그룹으로 나눴을 때 가능한 최소 비용 합 점화시은 아래와 같다. D[i][j] = min(D[k][j-1] + A[i] - A[k+1]) (for j-1 ≤ k < i) 총 시간복잡도는 $O(N^2M)$이다. #include #include using namespace std; int T, N, M; int A[101], D[101][101]; int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); s..

코드포스 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개의 행을 모두 덮는..

두 개의 요트가 있고, 요트를 이용하고 싶은 사람들의 예약 정보 시작 날짜, 끝 날짜, 대여 비용이 주어졌을 때, 최대 이윤을 구하는 문제다. 이 문제는 weighted interval scheduling의 확장판으로 two room weighted interval scheduling이다. 만약 요트가 두 개가 아니라 한 개라면 $O(N \lg N)$ Dynamic Programming 으로 해결할 수 있다. 이와 관련된 자료는 구글에 검색하여 쉽게 찾을 수 있다. 편의상 입력으로 주어진 예약(proposal)을 구간으로 표현하겠다. 이 문제를 $O(N^2)$ Dynamic Programming으로 해결할 수 있지만, 제한 시간을 초과한다. 이 방법에 대한 설명은 생략한다. 문제 입력 형식에 가장 중요한..

버스를 타는 버스 정기권과 버스와 기차를 모두 타는 전체 정기권이 기간 별로 주어지고, 각 날 마다 버스와 기차 타는 회수가 주어졌을 때, $N$일 동안 버스와 기차를 타는 최소 비용을 구하는 문제다. 문제에서 정기권의 기간과 요금, 그리고 단일 회수로 탑승할 때의 비용은 입력과 상관없이 항상 같게 정해져있다. Dynamic Programming을 생각해볼 수 있다. D[i][j] = i번째 날 까지 버스와 기차를 타고, 현재 남은 버스 정기권의 기간이 j일 때 최소 비용 위와 같이 다이나믹 배열을 정의하자. 이처럼 정의하는 이유가 있다. 전체 정기권을 산 경우 정기권 기간내에는 고려할 사항이 아무 것도 없지만, 버스 정기권을 산 경우 정기권 기간 내에 전체 정기권을 사는게 더 이익일 수 있기 때문이다...

문제에서 toroidal triangular lattices와 toroidal hexagonal lattices에 대해 그림 예시가 있다. Triangular lattices는 $M$이 짝수이며, hexagonal lattices는 $M$, $N$ 둘 다 짝수란 조건이 있다. 이런 그래프에서 해밀턴 회로 중 임의의 하나를 찾는 문제다. 이 문제는 2014 인터넷예선 그리드 그래프 문제와 흡사하다. 아래와 같은 방법으로 정점 순회를 하면 해밀턴 회로가 된다. #include int T, M, N, P; int main() { int i, j; for (scanf("%d", &T);T--;){ scanf("%d%d%d", &M, &N, &P); puts("1"); if (P == 3){ for (i=0;i

2차원 평면에 점들이 $N$개 주어졌을 때, 동일한 크기인 정사각형 세 개로 모든 점들을 덮을 때 가능한 정사각형의 최소 크기를 구하는 문제다. 주어진 $N$개의 점을 포함하는 최소 직사각형을 생각하자. 서로 다른 점이 4개 이상일 때 아래와 같은 명제가 성립한다. 최소 크기의 정사각형 세 개로 모든 점을 덮을 때, 그 정사각형 중 하나는 직사각형의 네 꼭지점 중 하나의 점을 꼭지점으로 한다. 비슷한 상황으로 최소 크기의 정사각형 두 개로, 서로 다른 점 3개 이상을 모두 덮는다고 할 때, 아래와 같은 명제가 성립한다. 최소 크기의 정사각형 두 개로 모든 점을 덮을 때, 두 정사각형은 서로 대각으로 마주보는 두 꼭지점을 꼭지점으로 한다. 이분 검색으로 정사각형의 크기 $s$를 정하고 모든 점을 덮을 수 ..