8/30 Problem Solving

14466 소가 길을 건너간 이유 6 (G3)

 

모든 소들의 쌍에 대해서 다리를 건너지 않고 인접한 칸으로 이동해서 도착할 수 있는지 확인해주면 된다. BFS/DFS 중 아무거나 이용해도 된다.

 

http://boj.kr/95aadfb791fa4472a470b95b2aa37c5c

 

 

14452 Cow Dance Show (G4)

 

무대 크기 K가 될 수 있는 범위 안에서 답을 가정하고 parametric search를 한다. min heap을 이용해서 현재 K가 가능한지 판단한다. 초기에는 무대에 K마리의 소가 동시에 올라가고 그 후로는 가장 먼저 춤을 끝낸 소가 무대에서 내려가는 시간에 다음 소가 무대에 오르게 된다. 공연이 Tmax 내에 끝난다면 더 작은 K값을 탐색하고 그렇지 않다면 더 큰 K값을 탐색한다.

 

http://boj.kr/fd4d2bfb4ddb4a19b6d0462ed3c4ab36

 

 

14454 Secret Cow Code (G4)

 

주어진 문자열 s에 대해 함수 F(s)는 s 뒤에 s를 오른쪽으로 한글자 회전한 문자열을 덧붙이는 것이다. F를 무한히 반복하여 문자열을 확장한다. 주어진 N 제한이 10^18이므로 직접 문자열을 생성하는 것은 불가능하다. 재귀적으로 N이 문자열 F(s)에서 어느 부분에 속하는지를 빠르게 파악할 수 있다.

 

(base case)

1. 만약 n이 원래 문자열 s의 길이보다 작다면 n번째 문자는 단순히 s[n]이 된다.

 

(recursive call)

2. n이 절반보다 작은 경우 n은 F(s)의 첫번째 부분에 속한다. 따라서 길이를 절반으로 줄여서 재귀적으로 다시 탐색한다.

3. n이 정확히 절반에 해당하는 경우 이는 F(s) 두번째 부분에서 첫번쨰 문자에 해당한다. 즉 첫번째 s의 마지막 문자와 같다.

4. n이 절반보다 크다면 n은 F(s)의 두번째 부분에 속한다. 이때 n의 위치를 half+1만큼 줄여서 원래의 s 위치로 되돌린 후 다시 탐색한다. 이는 두번째 s의 위치를 첫번째 s의 위치로 맵핑하는 역할을 한다.

 

http://boj.kr/bc83026ee74a484aaff7f5fe6fa96c44

 

 

10423 전기가 부족해 (G3)

 

MST를 만들어야 하는데 발전소가 있는 위치는 이미 전기가 공급되고 있다. 발전소들을 연결하는 비용이 0인 가상의 간선을 이어준 후 MST를 만들면 된다.

 

http://boj.kr/4c4f73833e1f4d7bbe5fa4f69878d856

 

 

16724 피리 부는 사나이 (G3)

 

사이클의 갯수를 세주면 된다. 사이클 탐지를 올바르게 하기 위해서 visit 배열의 상태를 3가지로 나누었다. 0이면 방문하지 않음, 1이면 현재 탐색 중, 2이면 탐색 완료인 상태로 구분했다. 사이클을 발견한 시점에서 1인 곳을 방문했다면 새로운 사이클을 발견한 것이므로 답을 세주고 2인 곳을 방문했다면 이미 있던 사이클에 합류하는 것이므로 세주지 않는다.

 

http://boj.kr/edc312e289984920bc0fa65ad0362073