PS 이야기

문제에서 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

$N$개의 명제 $S_1, S_2, ..., S_N$이 있고, 명제들 사이의 관계가 주어졌을 때 모순의 여부를 판별하는 문제다. 명제는 참 또는 거짓일 수 있으며, 우리는 어떤 명제 $S_i$에 대해 참이라고 확신하거나, 참인지 거짓인지 모르는 경우 두 가지 상황이 있다. 관계는 세 가지 종류로 주어진다. 이 종류를 자세히 살펴보면 우리는 명제가 참인지 거짓인지 모를 때, 거짓이라고 가정해도 모순 판별 여부에 아무런 영향이 없음을 알 수 있다. 쉽게 말하자면, 참이라는 확신이 없을 때에는 거짓이라고 생각해도 무관하다. 위와 같은 사실을 알았을 때, 우리는 1번 종류와 3번 종류 관계를 잘 이용해서 참이라고 확신할 수 있는 명제들을 추려내면 된다. 참이라고 확신할 수 있는 명제들을 추려낸 뒤, 2번 종류 ..

비트 문자열이 있을 때, 각 자리의 비트를 switch 할 수 있는 규칙이 2가지 있다. 이 두 가지 규칙을 통하여 주어진 비트 문자열의 모든 자리를 0으로 만드는 최소 회수를 구하는 문제다. 문제를 뒤집어 모든 자리가 0으로 되어 있는 비트 문자열에서 입력으로 주어진 비트 문자열을 만들기 위한 최소 회수를 구하는 문제로 바꾸자. 그러면 이제 왼쪽에 있는 1비트 부터 차례대로 만드는 것이 회수를 최소화 한다. 아래와 같은 값을 미리 계산해둔다. D[i] = 비트문자열의 모든 자리가 0이라고 할 때, 오른쪽에서 i번째 비트를 1로 만드는 최소 회수 D[i] = D[i-1]*2+1, D[1] = 1 D[i] = 2^i - 1 가장 왼쪽에 있는 1비트를 만들기 위한 최소 회수는 몇 일까? 그 비트의 위치를 왼..

자동차가 C대 있고 각 자동차의 시작 위치가 다를 수 있다. 모든 자동차의 목적지는 1번 마을이고, 각 자동차는 최단 경로 중 임의의 한 경로로 이동한다고 하자. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없을 때, 목적지에 갈 수 있는 자동차의 최대 개수를 구하는 문제다. 이 문제는 2013년 월드 파이널 C번 문제와 지문 하나 다르지 않게 출제되었다. 다행히도 이 문제의 풀이를 미리 알고 푼 팀은 없는 것으로 알고 있다. 문제에서 제약 조건은 단 하나, 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없다는 것이다. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동하기 위한 필요충분조건은 두 자동차의 시작 마을에서 도착 마을로 가는 최단 거리가 같다는 조건이다. 따라서 자동차..

길이가 N인 문자열이 주어지고, 길이가 M인 패턴이 주어진다. 이 패턴의 연속된 일부분 혹은 전체를 한 번 뒤집어서 새로운 패턴들을 만들 수 있다. 길이가 N인 문자열에서 이렇게 만들어진 패턴들과 매치되는 부분 문자열이 몇 개인지 세어주는 문제다. N ≤ 1,000,000 이고 M ≤ 100 이다. 시간제한은 0.2초로 N에 선형인 시간복잡도를 요구한다. 길이가 M인 패턴에서 뒤집는 연산에 의해 만들어지는 새로운 패턴의 개수는 많아야 $M^2$개다. 즉, 이 문제는 길이가 M인 패턴 $M^2$개와 길이가 N인 문자열을 매칭하는 문제로 바꿀 수 있다. 이와 관련된 문제는 Aho-Corasick 자료구조를 이용하면된다. KMP와 같은 문자열 매칭 알고리즘은 하나의 패턴과 전체 문자열을 매칭하는 알고리즘인데,..