상위 99.99%의 PS

https://www.acmicpc.net/problem/21735 21735번: 눈덩이 굴리기 눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은 www.acmicpc.net 비트마스킹 0이면 2칸, 1이면 1칸 이동 Python 코드 1 2 3 4 5 6 7 8 9 10 11 n,m=map(int,input().split()) a=list(map(int,input().split())) s=0 for i in range(1> n >> m; for (int i=0;i> a[i]; } int bit = 1

https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리 N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의 www.acmicpc.net [사용한 알고리즘] Smaller to Larger Technique https://justicehui.github.io/medium-algorithm/2019/09/23/small-to-large/ 이 글을 통해 공부했습니다 1. 쿼리를 뒤집는다. 2. 그러면 간선 제거를 간선 연결로 볼 수 있다. 그럼 엄청 쉬워진다 Union-Find를 통해 구현했고, 말 그대로 작은거를 큰거에..

www.acmicpc.net/problem/14180 14180번: 배열의 특징 첫째 줄에 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄에는 Ai (|Ai| ≤ 1,000,000)가 주어진다. www.acmicpc.net 배열 t에서, \(A_{i} = t_{1} 부터 t_{i} 의 합\) B = 배열 t의 특징 이라고 하면, 배열 t의 n번째 수를 옮길 떄의 최댓값을 dp[n]이라고 하면, 이 n번째 수를 옮기는 방향에 따라 두가지로 나누어 풀면 된다. 왼쪽으로 옮길 때는, \(i= getX(k[-3], k[-2]): k.pop(-2) def bs(x): lo = 0 hi = len(k) - 2 while lo

www.acmicpc.net/problem/2315 2315번: 가로등 끄기 첫째 줄에는 2개의 정수 N(1 ≤ N ≤ 1,000), M 이 있다. 첫 번째 정수 N은 가로등의 개수를 나타내는 정수이고, 두 번째 정수 M은 마징가 처음에 위치하는 가로등 번호이다. 다음 N 개의 줄에는 각 가 www.acmicpc.net dp 진짜 개재밌게 풀었다. 이동은 바로 옆의 켜진 가로등으로만 하는 것이 이득이다. dp테이블은 구간 \([l,r]\)에서, 내 위치가 \(x\)일때 최솟값으로 나타내면 된다. 공간은 1000*1000*2를 사용한다. 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 impor..

www.acmicpc.net/problem/11693 11693번: n^m의 약수의 합 nm의 모든 약수의 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 등비수열의 합 이용 예를 들어 \(2^2 \times 3^3\) 으로 소인수분해가 되는 수가 있다고 할때, 이 수의 약수의 합은 \((1+2^1+2^2) \times (1+3^1+3^2+3^3)\) 이다. 어떤 수 \(N\)과 소수 \(p\)에 대해, \(N = p^x\times C\) (\(C\)는 자연수) 로 나타낼 수 있다고 해보자. 이때, \(N^M = p^{xM} \times C^M\) 이므로, 소수 \(p\)에 대해 첫째항이 1이고, 공비가 \(p\)인 등비수열의 제 1항부터 제 \((xM+1)\)항까지..

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 = (..