본문 바로가기

백준

BOJ 17187 - Necklace (P1), BOJ 22195 - Necklace 4 (D5) 둘은 메모리 제한만 다른 문제이다. 사용 알고리즘더보기kmp 풀이더보기두 문자열을 s, t라 하자. 뒤집는 경우는 s든 t든 하나만 뒤집고 똑같이 하면 되니 뒤집는 경우는 고려하지 않아도 된다.t = A+B로 쪼개고 r = B + '$' + s + '#' + A 꼴로 된 문자열을 생각해보자. 중간에 $와 #는 문자열을 구분짓기 위한 dummy이다.예를 들어, s = "yxbadctz", t = "dcbayxz"일 때 A = "dc", B = "bayxz"가 가능하다.r = "baxyz$yxbadctz#dc"가 된다. 이제 여기서 r의 fail function과 rev(r)의 fail function을 구한 다음 $와 # 사이에 있는 인덱스 i를 순회하면서 fail_r{i} + fail_rev(r){|r|.. 더보기
BOJ 18083 - Disposable Switches (D5) 지금까지 푼 CHT 문제들 중에 CHT를 가장 특이하게 쓰는 것 같다. 사용 알고리즘dp, Convex Hull Trick 풀이가장 먼저 관찰해야 하는 사실은 v가 영향을 줄 수 없다는 것이다. 왜냐하면 v>0이므로 처음부터 v가 나눠져 있었다고 생각하면 된다.결국 각 간선의 가중치는 l + c가 되고, 최단 경로의 간선 개수에 영향을 받음을 알 수 있다. 이제 다음과 같은 dp를 정의하자.dp[i][j] := 1번 정점에서 i번 정점까지 도달하는 데에 j개의 간선을 사용했을 때의 최단 경로이는 O(N(N+M))에 계산할 수 있다. (다익스트라를 이용한 O(N(N+M)logNM)은 TLE를 받는다.)이렇게 구한 dp[n][i](1 f_i(x) = i*x + dp[n][i]라는 직선을 생각해보자. 이 직.. 더보기
BOJ 26973 - Circular Barn (P3) 계절학교 시즌이 되기도 했고 해서 적당히 실력에 맞는 USACO 문제들을 풀어보려 한다.tag더보기solved.ac 태그 : ad_hoc, dp, game_theory, math, number_theory, primality_test, sieve작성자 풀이 태그 : (동일) 풀이더보기일단 n = 1인 게임부터 생각해보자. 여기서 중요한 사실은 소수인것도 있지만 1, 2, 3만큼 소를 뺄 수 있다는 점이다. 먼저 소가 4마리일 때 Nhoj가 이기고(4는 소수가 아님), 소가 4의 배수에서 4의 배수가 아니게 되었을 때, 4k + a(0  하지만 이 문제에서는 이러한 게임을 2턴씩 n개를 순서대로 진행한다. 그럼 각 게임은 독립적이므로 내가 이기는 게임의 경우 최대한 빨리 끝내고, 지는 게임의 경우 최대한 .. 더보기
BOJ 32070 - 색깔 모으기 (P5) 24년 KOI 2차 초등부 3번, 중등부 2번이다.체감상 중등부는 2번, 3번, 4번 난이도가 다 똑같은데 이게 맞나?그건 그렇고 이 문제 풀이가 정말 재밌어서 풀이를 써보겠다. 먼저 \( A_{i} \) -> \( B_{i} \)을 간선으로 하는 그래프를 생각해보자. 만약 \(  A \)가 순열이라면(위에 놓여 있는 공의 색이 모두 다름) 이 그래프는 여러 개의 사이클로 이루어져 있을 것이다. 그리고 이 사이클대로 따라가면서 공을 옮기다 보면 그 사이클의 공을 모두 같은 색끼리 모을 수 있으며, 이 때 옮기는 횟수는 (사이클 크기) + 1이다. (사이클 크기가 1인 경우는 예외로 옮길 필요가 없다.) 따라서 답은 저 (사이클 크기) + 1을 모든 사이클에 대해서 더해준 값이 된다.그럼 \( A \)가 .. 더보기
BOJ 16182 - Dumae (D5) 사용 알고리즘Greedy(pq) + Topological Sorting 풀이일단 자명하게 DAG가 아니면 -1이다.그래프의 순서 관계도 있고 [L,R] 조건도 있어서 까다로울 수 있다. 결론부터 말하면 이 둘을 합치면 된다.대충 이런 그래프가 있다고 하자. 여기서 1번 노드는 자기만 보면 1번째 순서가 될 수도 있고 2번째 순서가 될 수도 있다. 하지만 바로 아래 노드(2번)를 고려하면 반드시 1번째 순서가 되어야 함을 알 수 있다. 이 조건을 [L,R]로 표현하려면 어떻게 해야 할까?위 상황에서 \( R_{2} = 2 \)이다. 그 말은 2번 노드는 2번째 순서 안에 선택되어야 한다. 그리고 2번 노드가 선택되려면 1번 노드를 먼저 골랐어야 하므로 적어도 1번 노드는 2번째 순서보다 한칸 앞선 1번째.. 더보기
BOJ 31232 삼국지, BOJ 31750 Split the GSHS 3 (P2,P1) 두 문제는 다음과 같다. 트리에서 간선을 두 개 끊어서 세 컴포넌트로 나눌 때 각각 컴포넌트의 가중치 합을 a,b,c(a 더보기
BOJ 10014 - Traveling Saga Problem (D1) 사용 알고리즘 Centroid Decomposition 풀이 일단 기본 아이디어는 트리와 쿼리 5와 비슷하지만 반대의 기능을 가진 쿼리를 이용한다. 트리와 쿼리 5는 다음과 같은 두 가지 쿼리를 구현해야 한다. 1. 정점 집합에 i번 정점을 추가/삭제한다. 2. 집합에 포함된 정점들 중 임의의 정점 v와 가장 가까운 정점과의 거리를 구한다. 여기서 2번 쿼리를 다음과 같이 수정해서 이용한다. 2. 집합에 포함된 정점들 중 임의의 정점 v와 가장 먼 정점을 구한다. 비슷해 보이지만 가장 가까운 거리와는 다르게, 가장 먼 거리는 centroid tree 상에서 조상들을 보면서 올라갈 때 같은 서브트리에 속한 정점을 고려하면 거리를 제대로 구하지 못하기 때문에, 자신이 속한 서브트리를 제외하고 가장 먼 거리를.. 더보기
BOJ 24547 - mod와 쿼리 (D4) 사용 알고리즘 Segment Tree, Sqrt Decomposition, Number Theory(Harmonic Lemma) 풀이 쿼리 1번은 잘못 보면 그냥 단순한 합 문제로 보이지만, 시그마 안에 mod가 있어서 단순한 문제는 아니라는 걸 알 수 있다. (이 사실을 코드 짜고 예제 1번 돌려보기 전까지 몰랐다.) 하지만 그렇게 어려운 문제도 아니다(?). X의 범위에 따라 나눠서 처리하면 되는데, X 316일때는 크기 X칸의 버킷에 따라 mod X할 때 빼야하는 X의 개수가 다르다는 점을 이용해 O(10^5/X)에 처리할 수 있다. 쿼리 2번은 좀 더 복잡하다. 일단 mod의 정의를 이용해 단순화해보면 이 쿼리는 \( nX - \sum A_{i} * \left \lfloor \frac{X}{A_{.. 더보기

티스토리툴바