7/30 ~ 7/31 연습

3584. 가장 가까운 공통 조상

문제 : http://icpc.me/3584

옛날 ICPC문제여서 그런지 진짜 LCA를 대놓고 묻는 문제. 이 때는 아직 LCA가 고ㅡ급 알고리즘이었나보다. 테스트 케이스마다 배열 초기화에 주의하도록 하자.

LCA에 대해서는 더 잘 설명해놓은 글들이 천지빽가리.

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220820773477

Time Complexity : \(O(Tn)\)

---

8984. 막대기 (KOI '13)

문제 : 

http://icpc.me/8984

http://oj.uz/problem/view/KOI13_game

BOJ AC 기준으로 게시.

문제 조건을 잘못 이해해서 이거 완전 NP 아니냐? 하고 풀이를 깠다. 이해가 1도 되지 않아서 문제 조건 다시 읽어보고 얼굴을 감쌌다.

맞는 풀이를 제시했던 갓-willi19에게 미안해지는 시점.

일단 수의 범위가 크니 좌표 압축을 하자. 좌표 압축은 lower_bound 등을 이용해 임의의 크기를 갖는 array \(x_1 < x_2 < \cdots < x_n\)을 \(1,2,\cdots n\)으로 압축해서 배열의 index로 사용할 수 있게 만드는 테크닉이다. 복잡도는 당연히 \(O(n lg n)\).

좌표 압축 이후에 모든 막대기를 정렬하자. 기준은 위쪽 좌표가 작은 순서대로. 위쪽 좌표가 같다면 아래쪽 좌표가 작은 순서대로.

모든 가능한 지그재그 선은 위쪽 좌표, 아래쪽 좌표가 증가하는 순서로 배열할 수 있으므로, 그냥 정렬된 막대기들을 차곡차곡 쌓아나가면서 지그재그 선 길이의 최댓값을 구하면 그놈이 답이 된다는 것을 알 수 있다.

따라서 \(2\times n\) DP array를 잡고, \(k\)번 막대기 \(s_k , e_k\)를 추가했을 때 (길이 \(L_k\)) 

\(DP[0][s_k]\)에 \(max(DP[0][s_k], DP[1][e_k]+L_k)\), \(DP[1][e_k]\)에 \(max(DP[1][e_k],DP[0][s_k]+L_k)\)를 넣으면서 갱신하면 된다. 최종 답은 모든 \(DP\)값 중 최댓값.

Time Complexity : \(Compression(n) + Sort(n) + O(n) = O(n lg n)\)

---

1405. 미친 로봇

문제 : http://icpc.me/1405

백트래킹인데, BFS식으로는 풀기 힘들고 DFS를 이용하면 금방 풀린다.

\(30 \times 30\) 정도 되는 visited 배열을 잡고, \((15,15)\) 정도를 원점으로 잡는다.

어떤 점을 방문했을 때, 그 점이 이미 visited라면 0을 반환하고, (커팅) 아니라면 갈 수 있는 모든 방향(NWSE)에 대해서

(그 방향으로 갈 확률) * (그 점에서의 DFS값)을 다 더한 값을 반환하면 된다. DFS 탐색을 종료할 때 꼭 vis 배열을 0으로 reset해주자.

나는 원래 왔던 곳(parent)으로 돌아가지 않게 if문을 넣어줬는데, 생각해보니까 그냥 무시해도 다음 단계에서 커팅되니까 시간 절약이 별로 안 되는 것 같다... 

Time Complexity : \(O(4 \times 3^{n-1}) = O(3^n)\)