전체 글
[백준 7993] 후르츠 치킨
1. 풀이 이 문제에서 핵심은 "멕카시나가 있는 도시에서 구사과의 집으로 향하는 모든 경로는 어떤 특정한 도로를 지나도록 되어있습니다"이다. 이 특정한 도로를 찾으면 문제 해결의 실마리가 보인다. 먼저 이 특정한 도로 \(u, v\)를 찾았다고 해보자. 이 간선을 없애면 치킨집만 존재하는 트리, 구사과의 집만 존재하는 트리로 나뉘어진다. 그렇다면 전자의 트리의 루트를 \(u\), 후자는 \(v\)라 하면 각 트리로 가는 최단 경로가 나올 것이다. 트리니까 그냥 레벨 차이가 최단 경로이다. 또한 문제 조건에 한 간선은 동시에 배달원 한명만 가능하다고 나와있다. 이 조건은 그냥 트리로 가는 최단 경로를 싹다 구해두고 같은 최단 경로가 있다면 +1을 하는 방법으로 중복이 없게 만들어 주면 된다. 그 후 치킨집..
[백준 1608] 스타 대회
1. 풀이 그래프끼리 컴포넌트를 나누자. 컴포넌트가 \(2\)개 이상이면 모두 승리가 가능하다. 그렇다면 컴포넌트가 \(1\)개인 경우만 생각하자. 잘 관찰을 하면 \(a\)에서 \(b\)로 도달할 수 있는 경로가 존재한다면 경로에 있는 모든 사람들을 패배하게 하고 \(a\)를 우승하게 만들 수 있다. 그러면 SCC로 묶어 본다는 생각을 해볼 수 있다. SCC로 압축한 그래프 DAG에서 \(level\)이라는 개념을 정의하자. DAG에서 새롭게 위상 정렬을 하면서 큐에 정점을 한번에 넣고, 한번에 처리하자. 큐를 처리할 때 마다 큐 안에 있는 \(level\)을 올라간다. \( level\)을 정의하면 아래의 사실을 쉽게 관찰할 수 있다. 1. \(i\)가 속한 SCC는 \(i\)에서 SCC안의 정점에 ..
[백준 7989] The Bridge
1. 풀이 먼저 남은 사람이 \(3\)명 이하면 잘 알아서 처리할 수 있다. \(4\)명 이상이면 잘 생각해보자 제일 적은 \(cost\)를 가진 두 명을 \(a,b(a < b)\)라 정의하고, 제일 많은 \(cost\)는 \(p, q(p < q)\)로 정의한다. 그렇다면 아래의 두 가지 행동을 취할 수 있다. 1. \(a, b\)를 같이 옮긴다. \(b\)를 다시 데리고 온다. \(p, q\)를 같이 옮긴다. \(a\)를 다시 데리고 온다. 그렇다면 \(a+2b+q\)만에 이 행동을 할 수 있다. 2. \(a, q\)를 같이 옮긴다. \(a\)를 다시 데리고 온다. \(a, p\)를 같이 옮긴다. \(a\)를 다시 데리고 온다. 그렇다면 \(2a+p+q\)만에 이 행동을 할 수 있다. 이 두가지 행동 ..
[백준 7987] Spies
1. 풀이 문제를 요약하자면 단방향 그래프가 주어지고 \(u, v\) 간선은 \(u\)가 \(v\)를 감시할 수 있다는 뜻이다. 그리고 \(v\)를 스파이로 정한다 했을 때 \(v\)를 연결하는 정점들 중에서 최소 한명이 스파이가 아니여야 된다. 이 규칙에 따라 스파이를 정할 때 최대 스파이 수를 구하는 문제이다. 무방향 그래프로. 생각해보면 무조건 한 컴포넌트에는 정점 \(N\)개와 간선 \(N\)개가 존재한다. 단방향 간선을 가진다 하여도 잘 생각해보면 한 컴포넌트에는 하나의 사이클이 존재하고 나머지는 사이클 내에 정점에 트리처럼 붙어 있는 형태이다. 트리에서 위 문제를 해결한다고 가정하면 \(dp[i][j]\) = (\(i\)번째 정점이 \(j\)가 \(0\)이면 스파이가 아니고, \(j\)가 \(..
[백준 1839] 트리 모델 만들기
1. 풀이 노끈 개수의 최솟값을 어떻게 구하는 지 먼저 생각해보자. 그리디하게 생각해보면 무조건 두 개의 노끈을 하나로 합쳐줄 수 있다면 그때마다 합쳐주는 것이 이득이다. \(1\)번을 루트로 탐색하면서 자식의 개수는 \(x\)라 하면 \(\frac{x}{2}\)개씩 노끈을 하나로 합쳐줄 수 있다. 그러므로 \(ans1 += \frac{x}{2}\)를 해주면 된다. \(x\)가 짝수라면 자식끼리 잘 연결 해주면 되고, 홀수라면 \(1\)개는 부모에서 오는 노끈에 연결하고 나머지를 잘 연결 해주면 된다. 그리고 \(1\)번 의 정점의 \(x\)가 홀수면 \(ans1++\) 해준다. 노끈 개수를 최솟값으로 하면서 노끈 길이의 최댓값을 최소로 하는 방법은 이분 탐색을 생각해볼 수 있다. 결정 문제를 "\(f(..
Polish Olympiad in Informatics 정리
test case : https://www.oi.edu.pl/old/php/show.php?ac=e140000 연도 Stage 1 2 3 4 5 6 7 POI 1995 Stage 1 Trees Ones And Zeros Disk Optimization Palindromes Stage 2
[백준 22349] 가장 긴 공통 괄호 문자열
1. 풀이 간단하게 접근을 시작하면 정답을 이분 탐색을 통해 찾을 수 있다. 일반적 이게 결정 문제 \(f(x)\)를 "\(x\)길이의 공통 괄호 부분 문자열이 존재하는가?" 로 정의한다. 그리고 각 \(A, B\) 문자열에서 \(x\) 길이의 연속한 부분 문자열을 올바른 괄호 문자열인지 확인한 다음 라빈 카프로 \(O(1)\)에 해싱한다. 해싱한 값을 가지고 있는 집합을 정렬한 뒤 이분 탐색을 통해 같은 해시 값들 동일한 괄호 문자열을 비교하여 해결해줄 수 있다. 어떤 구간이 올바른 괄호 문자열인지 확인하는 방법은 먼저 \(( = 1, ) = -1\)으로 정의한다. 그리고 구간 합 \(psum\)을 정의한다. \([l, r]\) 부분 문자열이 괄호 문자열인 충분 조건은 아래와 같다. seg는 \(psu..