A 솔직히 5분도 너무 오래 걸린것 같다..5분 pretest pass. AC+ : 결국 어떤 문자열 S, T가 있을 때 S를 적당히 rotate해서 T로 만들 수 있느냐를 묻는 문제였다. 계속반에서 비슷한 문제 (기하 문제였다) 를 KMP로 푸는 사람들이 꽤 있었는데, KMP에 숙달되었거나 라이브러리가 있는게 아닌 한, 시간 버리고 점수 와장창 까이기 딱 좋은 방법이다. 적당한 기준 원소를 아무거나 잡고 (난 std::min_element 를 사용했다.) 그쪽을 기준으로 rotate하는 것이 가장 좋은 방법이라고 생각. stl 떡칠시 아주 빠르게 짤 수 있다. 특히 std::rotate가 꿀. 난 문제를 너무 대충 생각해서 코딩 + 시간이 살짝 말린 채로 시작했고 그 부분이 아쉽다고 생각한다. (다행이..
https://www.acmicpc.net/problem/2795딱 봐도 NP-hard같은 문제를 N = 100을 주고 출제한걸 보니 당황하지 않을 수가 없었다. 일단 유일하게 생각해 볼수 있을 만한 접근법은 http://koistudy.net/?mid=prob_page&NO=369 와 같은 류의 바이토닉 기반 DP인거 같다. 한번 그 점을 생각해보고 어떠한 식으로 DP를 짜야지 최적 경로를 고려하는 점화관계를 이끌어낼 수 있는지 알아보자. 일단 생각을 쉽게 하기 위해서 1 -> 2로 가는 임의의 경로를 고정시키고, 그 경로상에서 2 -> 1로 오는 경로를 그려놓았다.#1 같은 경우에는 그냥 플로이드 한번에 풀릴 거고#2 같은 경우에는 위 링크건 문제를 풀어봤다면 그렇게 어렵지 않다. 다음과 같이 dp를..
Hill Walk (USACO 2013.03 Gold)https://www.acmicpc.net/problem/5835x좌표를 쭉 증가시키면서, 현재 f(x) 값으로 정렬된 선분들을 들고 다니면 쉽게 풀 수 있다. 이런걸 하는 데 가장 좋은 툴은 뭐니뭐니해도 BST. 선분이 교차할 일이 없기 때문에 한번 삽입 할 때 제대로 삽입하면 끝까지 문제가 생기지 않음을 알 수 있다. 저런 정렬된 선분들을 제대로 들고 다니려면 1. comparator를 재정의해야 하고, 2. comparator의 반환값이 가변적이라는 사실에 언어가 x랄을 하지 않아야 문제를 풀 수 있다는 점을 유념해야 한다. 1번은 http://amugelab.tistory.com/entry/STL-priority-queue-%ED%99%9C%E..
- Total
- Today
- Yesterday