본문 바로가기

백준/플래티넘

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번 난이도가 다 똑같은데 이게 맞나?그건 그렇고 이 문제 풀이가 정말 재밌어서 풀이를 써보겠다. 먼저 Ai -> Bi을 간선으로 하는 그래프를 생각해보자. 만약 A가 순열이라면(위에 놓여 있는 공의 색이 모두 다름) 이 그래프는 여러 개의 사이클로 이루어져 있을 것이다. 그리고 이 사이클대로 따라가면서 공을 옮기다 보면 그 사이클의 공을 모두 같은 색끼리 모을 수 있으며, 이 때 옮기는 횟수는 (사이클 크기) + 1이다. (사이클 크기가 1인 경우는 예외로 옮길 필요가 없다.) 따라서 답은 저 (사이클 크기) + 1을 모든 사이클에 대해서 더해준 값이 된다.그럼 A가 .. 더보기
BOJ 31232 삼국지, BOJ 31750 Split the GSHS 3 (P2,P1) 두 문제는 다음과 같다. 트리에서 간선을 두 개 끊어서 세 컴포넌트로 나눌 때 각각 컴포넌트의 가중치 합을 a,b,c(a 더보기
BOJ 21099 - Four XOR (P4) 사용 알고리즘Pigeon Principle, Brute Force 풀이A,B,C,D는 대충 배열에서 서로 다른 4개를 뽑은 값이라 하자.A xor B xor C xor D = 0이므로A xor B = C xor D를 얻는다.즉 두 수를 xor한 값이 같은 순서쌍이 존재하는지 판별하는 문제와 동치이다.그럼 이제 이걸 어떻게 푸느냐?를 고민하면 굉장히 어렵다. 적어도 O(Nlog^2N) 정도에는 해야할 것 같은데 쉽지 않다. 아니 애초에 A xor B = k인 거 찾기도 O(NlogN) 정도는 걸린다.그런데 사실 이건 함정이다. 고민하다 보면, 가능한 순서쌍 개수는 O(N^2)개인데 이게 다 다를 수 있는가? 에 대한 의문을 가지게 된다. 한번 생각해보자.수 범위가 10^5 이하이므로 xor한 값은 범위가 .. 더보기
BOJ 8452 - 그래프와 쿼리 (P1) 사용 알고리즘 BFS + Offline Query 풀이 일단 간선 삭제 -> 뒤집으면 간선 추가는 유명하다. 그러고 나서 안될 것 같은 naive한 풀이를 짜면 된다. 그냥 간선이 추가되서 완화되는 정점들을 일일히 탐색하면 된다. 이게 되는 이유를 생각해보자. 1에서 각 정점까지 가는 최단경로는 O(N)일 것이다. (정점이 N개이므로) 그러므로 최단경로가 완화되는 경우도 O(N)일 것이다. 그리고 그러한 정점이 N개 있으므로 전체에서 완화되는 횟수가 O(N^2)이다. 그리고 O(M)개의 간선은 완화될때마다 한번씩 보게 되고, 완화되는 횟수는 말했듯이 정점당 O(N)이므로 간선을 O(NM)번 보게 된다. 따라서 그냥 구현해주면 되며, O(N(N+M)+Q)에 풀린다. 더보기 using namespace st.. 더보기
BOJ 14701 - 셔틀버스 (P3) 사용 알고리즘 Lazy propagation + binary search 풀이 학생들이 어떻게 이동하는지를 관찰해보자. 중앙을 기준으로 왼쪽에 있는 학생들은 무조건 1번 쪽으로 이동하고 오른쪽에 있는 학생들은 무조건 N번 쪽으로 이동할 것이다. 그리고 한 학생이 빠지게 되면 중간이 비고 2개의 연속된 그룹이 생기는데, 이 그룹끼리는 절대 서로 영향을 주지 않는다. (즉 한쪽 그룹에서 학생이 빠졌는데 다른 그룹의 학생이 이동하는 일은 없다는 뜻이다) 따라서 한명이 일단 빠졌다고 하자. 이 한명이 어떤 형태로 빠지는지는 N이 홀수인 경우와 짝수인 경우로 나눠 관찰하면 쉽게 찾을 수 있다. 이제 필요한 관찰은 다음과 같다. 1. 어떤 학생이 빠질 때 학생들의 번호는 항상 순서대로 유지된다. 2. 어떤 학생이 .. 더보기
BOJ 25639 - 수열과 최대 상승 쿼리 (P1) 20240816 추가) 지금 보니 이 문제는 그냥 금광세그 기초 문제이다. 아래에 적혀있는 풀이는 금광 세그를 자력솔(!)한 것이다. 사용 알고리즘Segment Tree 풀이세그먼트 트리의 각 노드에는 3개의 값을 관리한다.(1) 담당하는 구간의 최댓값 (N_max)(2) 담당하는 구간의 최솟값 (N_min)(3) 담당하는 구간의 최대 상승 값 (N_up) (1), (2)는 G1짜리 간단한 문제이므로 생략한다. (3)을 어떻게 처리할지를 생각해야 하는데, 리프 노드면 구간이 1이므로 그냥 0이다.그럼 구간 크기가 2 이상인 노드의 최대 상승 값은 어떻게 구할까? 바로 max(R_max - L_min, R_up, L_up)이다. 이때 L은 현재 노드의 왼쪽 자식에서의 값이고 R은 오른쪽 자식에서의 값이다.. 더보기
BOJ 1201 - NMK (P3) 사용 알고리즘 Greedy-Style Constructive 풀이 BOJ 27244의 확장판이다. https://sehujeong.tistory.com/20에서 설명한 그룹을 확장해보자. 그룹의 크기가 최대 K이고, 그 개수가 M개면 똑같이 풀 수 있을 것이다. 따라서 N을 K+a1+a2+...+a_M-1 꼴로 나타낼 수 있으면 27244와 똑같다.(1k; if(!(m+k-1 더보기

티스토리툴바