PS 이야기

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번 종류 ..