PS 이야기

두 개의 요트가 있고, 요트를 이용하고 싶은 사람들의 예약 정보 시작 날짜, 끝 날짜, 대여 비용이 주어졌을 때, 최대 이윤을 구하는 문제다. 이 문제는 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$를 정하고 모든 점을 덮을 수 ..

문제에서 well-formed라고 정의된 'a'와 'b'로만 구성된 문자열 A와 B가 주어진다. 두 인접한 문자를 바꾸면서 문자열 A를 문자열 B로 만드는 최소 회수를 구하는 문제다. 문자 'a' 를 '(' 로 바꾸고 문자 'b'를 ')'로 바꾸면 괄호 문자열이 되고 well-formed의 정의가 직관적이게 된다. 이 문제에서 문자열 A를 문자열 B로 바꿀 수 없는 경우는 두 문자열의 길이가 다른 경우 뿐이다. 문자 두 개로만 구성된 문자열이기 때문에 바꾸는 최소 회수 또한 직관적이게 생각할 수 있다. #include #include #include using namespace std; #define MAXN 100005 int T, N, M; char A[MAXN], B[MAXN]; int main()..

노드가 $N$개인 트리가 주어진다. 트리의 간선에는 비용과 이익 두 가지 값이 있다. 우리는 임의의 경로를 선택하는데 경로에 있는 간선의 비용 합이 C를 넘지 않으면서 이익 합의 최대값을 구하는 문제다. 트리에서 경로는 연결되어 있으면서 경로를 부분 그래프로 봤을 때 정점의 차수가 3을 넘으면 안된다. 즉, 갈래가 없으면 안된다. 이 문제는 IOI 2011 Race 문제와 굉장히 유사한 면이 있다. 우선 분할 정복으로 접근할 수 있다. 이는 트리에서 아래 조건을 만족하는 정점이 항상 존재하기 때문이다. 관련 증명은 Race 문제의 글을 참고하자. 정점이 $N$개인 트리에서 어떤 점을 지웠을 때, 생기는 여러 개의 서브트리 중 정점의 개수가 가장 많은 서브트리의 정점 개수가 $\frac{N}{2}$ 이하다..

1 부터 $N$ 까지의 수 $N$개가 포함된 순열이 주어졌을 때 문제에서 정의한 그래프를 그릴 수 있다. 그 그래프에서 포함된 회로(cycle)의 개수를 세는 문제다. 순열로 표현한 그래프의 특징상 회로의 개수는 곧 연결 요소의 개수가 된다. 따라서 DFS, BFS 등 여러 가지 방법으로 Flood-Fill 을 하여 연결 요소의 개수를 구하면 된다. #include int T, N; int A[1001]; bool V[1001]; void dfs(int n) { if (V[n]) return; V[n] = 1; dfs(A[n]); } int main() { int i; for (scanf("%d", &T);T--;){ scanf("%d", &N); for (i=1;i

빨강, 파랑, 초록색, 세 가지 색상의 공들이 2차원 평면에 배치 되어 있다. 빨간색 공을 세는 직사각형, 파란색 공을 세는 직사각형, 초록색 공을 세는 직사각형 세 개를 크기 제한 없이 겹치지 않게 잡았을 때 세어지는 공의 개수를 최대화 하는 문제다. 여기서 직사각형 변 위에 있는 공도 세어주고, 겹쳐서는 안된다. 우선 직사각형의 크기 제한이 없다는 점을 생각하자. 그러면 가능한 직사각형의 배치를 아래와 같이 크게 두 가지로 나눌 수 있다. 이 두 가지 경우에 대한 코딩을 하고 y축 대칭, 직선 y=x에 대한 선대칭 및 $3! = 6$가지의 색상 재배열등을 행해 모든 경우를 고려할 수 있다. 우선 각 점들을 x 좌표 기준으로 정렬을 한 뒤 빨간색 영역이 차지하는 범위를 정한 뒤 segment tree ..

정점의 개수가 $N$개고 간선의 개수가 $M$개인 그래프가 주어진다. 각 정점의 차수가 $K$ 이상인 부분그래프 중 가장 큰 부분그래프의 크기를 구하는 문제다. 입력으로 주어진 그래프에서 차수가 $K$ 보다 작은 정점들은 답이 되는 부분그래프에 들어갈 수 없으므로 제거한다. 그런 정점들을 제거하면 새로운 그래프가 나오는데, 마찬가지로 새로운 그래프에서도 차수가 $K$ 보다 작은 정점들은 답이 되는 부분그래프에 들어갈 수 없다. 위와 같은 방법으로 더 이상 제거할 정점이 없을 때까지 정점들을 제거한다. 그 후 남은 그래프가 문제에서 요구하는 최대 크기의 부분그래프가 된다. 총 시간복잡도는 $O(M)$이 된다. #include #include using namespace std; #define MAXN 20..

3 이상 1000 이하 자연수 $K$가 주어졌을 때, $K$를 정확히 3개의 삼각수의 합으로 표현할 수 있는지 판별하는 문제다. $K$는 1000 보다 크지 않으므로, 1000 이하의 삼각수 44개를 이용하여, 삼 중 for문으로 가능한지 판별할 수 있다. 테스트케이스 별로 삼 중 for문을 쓰면 시간 초과 될 여지가 있으므로, 전처리를 하면 좋다. #include int T,A[45],D[1001]; int main() { int i, j, k; for (i=1;i