상위 99.99%의 PS

BOJ 3683 - 고양이와 개 싫어하는 것에 대하여 충돌이 일어나는 사람을 향하는 간선을 추가해주면 된다. 이분매칭을 진행하고 v - max가 답이다. BOJ 1202 - 보석 도둑 무게가 가벼운 보석부터 보면 된다. 우선순위 큐를 이용하여 C_i보다 가벼운 보석들 중에 가장 비싼걸 가져가면 된다. BOJ 9006 - 다리 먼저 좌표 순으로 정렬한다. 그리고 왼쪽 다리는 m, 오른쪽 다리는 n의 가중치를 두고 nm에서 가중치를 빼다가 양수가 아니게 될 때가 답이 된다. BOJ 9484 - 최대삼각형, 최소삼각형 Rotating Sweep Line Technique 기초문제이다. 두 점을 잇는 선분을 기준으로 왼쪽과 오른쪽에서 각각 먼 점과 가까운 점을 뽑고 넓이를 계산하면 된다. O(N²lgN)

78분 만에(백준 채점 현황에 그렇게 뜨니까 맞겠지?) 올솔을 하고 1등상으로 키보드를 받았다. 기분이 매우매우 좋다! 내가 푼 순서대로 풀이를 쓰겠따 ----------- 1분정도 A를 보다가 지문이 약간 이해가 안 돼서 B로 넘어갔다. B 청정수열 (Easy) (00:04) 1부터 n까지, 11223344...nn 으로 나열하면 최소이다. 이때, 11,22,33,nn의 n개를 나열하는 경우의 수는 n! 이다. C를 보자마자 압도적인 지문 길이를 보고 바로 D로 넘어갔다. D 두라무리 휴지 (00:10) 그냥 구현하면 된다. 단어의 글자들을 재배열해서 어떤 단어를 만들수 있는지는 글자의 등장 횟수를 비교하면 된다. F번을 보다가, 18로 나눈 후 케이스 나누는 것이 귀찮아서 E로 넘어갔다. E 베스킨라..

배열 문제가 800번째 문제였다는걸 깨달았다. 다음 목표는 900솔 1000솔보다 퍼플을 찍고싶은 마음이 더 크다.

https://codeforces.com/contest/1670 https://codeforces.com/contest/1670 codeforces.com A (01:49) +5 음수의 개수와 양수의 개수 중 적은 것을 k라고 하면, 왼쪽 k개는 음수로 하고 나머지는 양수로 하면 풀린다 B (00:29) Special Letter 전까지의 알파벳 개수가 답이다. SAAAAS은 4가 아니라 5임에 유의 C (01:00) +3 \(a_i\)에서 \(b_i\)로 가는 간선들을 추가해주고, 크기가 2 이상인 사이클의 개수를 \(i\)라고 했을 때, \(2^i)가 답이다. D (01:51) +2 직선의 기울기에 따라 a, b, c로 나누어보자. a, b, c의 개수들 중 가장 많은 두 종류의 직선을 지나도록 그으..

https://www.acmicpc.net/problem/13159 13159번: 배열 [1, 2, 3, 4, 5]→[1, 4, 3, 2, 5]→[1, 4, 5, 3, 2]→[5, 1, 4, 3, 2] www.acmicpc.net [알고리즘 분류] 스플레이 트리 2번정도 구현해보기만 했던 스플레이 트리.. 막상 해보니 그렇게까지 어렵지는 않았다. 아마도..? https://cubelover.tistory.com/10 위 글을 참고하였다. 감사합니다.. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51..

https://codeforces.com/contest/1673 Dashboard - Codeforces Round #785 (Div. 2) - Codeforces codeforces.com 기쁘다. 4솔이 잘 돼서 코포 의욕이 마구 생긴다! 다음 목표는 1시간 안에 4솔 가볍게 하기 + 남은 1시간 안에 2E 솔브. A (00:04) 짝수면 알파벳의 합. 홀수면 한쪽 끝의 알파벳 한 개만 빼고 합 비교하기 더보기 28줄부터 보면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 impo..

https://www.acmicpc.net/problem/10227 10227번: 삶의 질 첫째 줄에 4개의 정수 R, C, H, W 가 주어진다. R과 C는 각각 도시의 행과 열의 크기를 나타내고, H와 W는 각각 홍준이가 정한 영역에서의 행과 열의 크기이다. 그 다음 R개의 줄에 각각 C개의 quality ran www.acmicpc.net [알고리즘 분류] 이분 탐색, 누적 합 정답을 \(x\)라고 가정하자. 주어진 배열에서 \(x\)보다 큰 수는 1, 작은 수는 -1로 바꾼다면, 합이 0인 \(H\) x \(W\) 직사각형이 배열 내에 존재할 것이다. 이 아이디어를 이용하여 이분 탐색으로 적절한 \(x\)를 찾을 수 있고, 시간복잡도 \(O(RC(lg(RC)))\)에 문제를 풀 수 있다. 75줄부..

https://www.acmicpc.net/problem/20669 20669번: Close to You 임베디드 개발자인 진우는 방구석에서 데이터 시트만 보며 허무한 학창 시절을 보냈다. 하지만 주변 친구들의 수많은 구원의 손길 끝에, 소개팅에서 만난 한콩이와 장거리 연애를 시작했다! 모 www.acmicpc.net [알고리즘 분류] 수학 https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=gt7461&logNo=110151975370 인접행렬과 인접행렬의 거듭제곱 (문제) 아래 그래프의 꼭짓점 P에서 R까지 3개의 변을 거쳐가는 모든 방법의 수는? ※ 이산수학에서 '그... blog.naver.com 이 글을 참고하였다. (N + ..

https://codeforces.com/contest/1671 Dashboard - Educational Codeforces Round 127 (Rated for Div. 2) - Codeforces codeforces.com E솔이 무려 500명정도가 나왔던 쉬운 라운드. 하지만 나에겐 아직도 어렵다 A (00:02) 2글자 이상의 연속된 문자는 무조건 만들수 있다. 단순 구현문제 B (00:07) x - 1, x, x + 1은 뭔가 좀 불편하니까 x - 2, x - 1, x로 보면, 바로 전 수에 맞춰서 값을 빼기만 하면 된다는 사실을 금방 알 수 있다. 이것도 단순 구현문제 C (00:25) 가격이 싼 것부터 사는게 당연히 이득이므로, 정렬 후 누적합 배열을 만든다. 그리고 각 물품마다, 어느 날..

https://www.acmicpc.net/problem/17634 17634번: 이상한 기계 첫 번째 테스트에서, 이 기계는 시점 4에서 (2, 1)을, 시점 7에서 (0, 1)을, 시점 8에서 (1, 2)를, 시점 9 에서 (0, 0)를, 시점 17에서 (1, 2)를, 시점 18에서 (0, 0)를 출력한다. 따라서 서로 다른 네 개의 순서 www.acmicpc.net [사용한 알고리즘] 라인 스위핑, 정수론 greedev에게 APIO 문제를 추천해달라고 해서 받은 문제다. 간단하고 재미있는 식정리이다. \(t = Bp + q\) (p, q 서로소 아님) 으로 두면, \(x = ((B + 1)p + q) \hspace{0.15cm} mod \hspace{0.15cm} A\) \(y = q\) 가 된다...