2017. 8. 1. 02:04ㆍ알고리즘 문풀/BOJ 연습
3584. 가장 가까운 공통 조상
문제 : http://icpc.me/3584
옛날 ICPC문제여서 그런지 진짜 LCA를 대놓고 묻는 문제. 이 때는 아직 LCA가 고ㅡ급 알고리즘이었나보다. 테스트 케이스마다 배열 초기화에 주의하도록 하자.
LCA에 대해서는 더 잘 설명해놓은 글들이 천지빽가리.
http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220820773477
Time Complexity :
8984. 막대기 (KOI '13)
문제 :
http://oj.uz/problem/view/KOI13_game
BOJ AC 기준으로 게시.
문제 조건을 잘못 이해해서 이거 완전 NP 아니냐? 하고 풀이를 깠다. 이해가 1도 되지 않아서 문제 조건 다시 읽어보고 얼굴을 감쌌다.
맞는 풀이를 제시했던 갓-willi19에게 미안해지는 시점.
일단 수의 범위가 크니 좌표 압축을 하자. 좌표 압축은 lower_bound 등을 이용해 임의의 크기를 갖는 array 을 으로 압축해서 배열의 index로 사용할 수 있게 만드는 테크닉이다. 복잡도는 당연히 .
좌표 압축 이후에 모든 막대기를 정렬하자. 기준은 위쪽 좌표가 작은 순서대로. 위쪽 좌표가 같다면 아래쪽 좌표가 작은 순서대로.
모든 가능한 지그재그 선은 위쪽 좌표, 아래쪽 좌표가 증가하는 순서로 배열할 수 있으므로, 그냥 정렬된 막대기들을 차곡차곡 쌓아나가면서 지그재그 선 길이의 최댓값을 구하면 그놈이 답이 된다는 것을 알 수 있다.
따라서 DP array를 잡고, 번 막대기 를 추가했을 때 (길이 )
에 , 에 를 넣으면서 갱신하면 된다. 최종 답은 모든 값 중 최댓값.
Time Complexity :
1405. 미친 로봇
문제 : http://icpc.me/1405
백트래킹인데, BFS식으로는 풀기 힘들고 DFS를 이용하면 금방 풀린다.
정도 되는 visited 배열을 잡고, 정도를 원점으로 잡는다.
어떤 점을 방문했을 때, 그 점이 이미 visited라면 0을 반환하고, (커팅) 아니라면 갈 수 있는 모든 방향(NWSE)에 대해서
(그 방향으로 갈 확률) * (그 점에서의 DFS값)을 다 더한 값을 반환하면 된다. DFS 탐색을 종료할 때 꼭 vis 배열을 0으로 reset해주자.
나는 원래 왔던 곳(parent)으로 돌아가지 않게 if문을 넣어줬는데, 생각해보니까 그냥 무시해도 다음 단계에서 커팅되니까 시간 절약이 별로 안 되는 것 같다...
Time Complexity :