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}$ 이하다..