상위 99.99%의 PS

www.acmicpc.net/problem/1396 1396번: 크루스칼의 공 첫째 줄에는 그래프의 정점의 개수 n과 간선의 개수 m이 주어진다. 그리고 두 번째 줄에서 m+1번째 줄까지는 a b c의 형태로 a와 b를 잇는 간선의 고유값이 c라는 의미이다. m+2번째 줄에는 알고 싶은 www.acmicpc.net 원래는 lca 공부하면서 풀려고 했는데, 누군가가 나보고 병렬 이분탐색 문제를 주면서 풀라고 하길래 이론만 강의로 듣고 다음날 까먹었다! 병렬 이분탐색에 대해서는 여기에 정말로 잘 나와있으니 모른다면 정독하고 오자. 열심히 구현했는데, 아직 완전히 내것이 된게 아니라 나중에 다시 한번 또 풀거다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..

www.acmicpc.net/problem/1994 1994번: 등차수열 N(1≤N≤2,000)개의 음 아닌 정수들이 있다. 이들 중 몇 개의 정수를 선택하여 나열하면 등차수열을 만들 수 있다. 예를 들어 4, 3, 1, 5, 7이 있을 때 1, 3, 5, 7을 선택하여 나열하면 등차수열이 된다. www.acmicpc.net 정렬 후 이분 탐색 이런거도 dp라고 보는지는 모르겠다.. dp로 푼거는 아닌듯 시간복잡도 \(O(N^2 logN)\) [Python] 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 import sys input = sys.st..

www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net Greedy 큰 수는 111..., 7111... 의 형태이고, 작은 수는 ???88888...의 형태이다. 노트에 몇번 끄적이다 보면 보인다. 큰 수는 홀수 짝수, 작은수는 7로 나눈 나머지에 따라 케이스를 나누어 풀어주면 된다 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 import sys input = sys.stdin.readl..

www.acmicpc.net/problem/16991 16991번: 외판원 순회 3 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 도시의 좌표 x, y가 주어진다. 모든 좌표는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 두 도시의 위치가 같은 경우 www.acmicpc.net DP using bitfield 외판원 순회 1과 똑같은 문제이다. 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 import sys from math import sqrt input = sys.stdin.readline INF = 1234..

www.acmicpc.net/problem/1306 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net 세그트리 기초문제이다. 최댓값 세그트리를 만들어두고, 시야 범위 내에서 최댓값을 찾는다. 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 seg = [0 for _ in range(4040404)] def init(n,s,e): if s == e: seg[n] = a[s-1] return seg[n] mid = (..

www.acmicpc.net/problem/17291 17291번: 새끼치기 실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다. 벌레는 기준 www.acmicpc.net dp로 풀 수 있고, 단순 구현으로도 풀수 있다. 나는 dp로 풀었다. 홀수년도와 짝수년도에 태어난 세포는 모두 짝수년도에 소멸하고, 소멸하는 수는 그 전년도의 세포의 수이다. 즉, i 년에 태어난 세포의 수 = (i - 1)년에 존재한 세포의 수이다. 점화식은, k가 짝수일 때, \(dp[k] = dp[k-1] * 2 - (dp[k-4] + dp[k-5])\) k가 홀수일 때, \(dp[k] = dp[k-1] *..

www.acmicpc.net/problem/1321 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 세그트리 기초문제?이다. 1~K번째 부대 인원의 수의 총합을 A_k라고 할때, x번 군인의 위치는 \(A_{k-1} \lt x \le A_k\) 를 만족하는 가장 작은 k가 되고, 이는 이분 탐색으로 빠르게 구할 수 있다. -소스코드 더보기 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 3..

www.acmicpc.net/problem/16895 16895번: 님 게임 3 구사과와 큐브러버가 님 게임을 하고 있다. 님 게임은 돌을 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진 www.acmicpc.net Sprague-Grundy Theorem.. 재밌다. O(MN^2) 로 브루트포스 돌리면서 님 합이 0이 된다면 ans에 1 더하는 방식으로 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 n = int(input()) a = list(map(int, input().split())) ans = 0 for i in range(n): for j in range(1, a[i]+1): p = a[i..

www.acmicpc.net/problem/17371 17371번: 이사 $(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의 www.acmicpc.net 편의시설을 집으로 쓸 수 없다는 조건이 없기 때문에, 문제가 매우 쉬워졌다. 그냥 편의시설을 집으로 쓰면 된다. 집과 가장 가까운 편의시설의 거리는 0이 되므로, 가장 먼 편의시설과의 거리만 계산해주면 O(N^2)에 풀 수 있다. N제한도 1000밖에 되지 않아 충분하다! 집을 편의시설로 정하는게 왜 되는건지는 직접 증명..

www.acmicpc.net/problem/13263 13263번: 나무 자르기 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 b2 > ... > bn을 만족 www.acmicpc.net CHT 기초문제이다. 아래 자료를 먼저 읽고 온다면 도움이 된다. stonejjun.tistory.com/50 m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221418495037&proxyReferer=https:%2F%2Fwww.goog..