상위 99.99%의 PS

과제 이슈때문에 골드 이하로만 풀었다. 근데 왜이리 어렵지? BOJ 24270 - 미니 버킷 리스트 (G4) 더보기 이게 골4 난이도인지는 잘 모르겠다. \((N + 1)\)개의 구간에 아무것도 안 하는 단위시간 \(K - sum(S)\)개를 채우는 문제이고, \(_{N+1}H_{K-sum(S)}=_{N+K-sum(S)}C_{N}\)을 계산하는 문제가 된다. BOJ 24269 - 랜드마크 건설 (G2) 더보기 Case Work. 직사각형의 테두리에 건물 3개를 짓는 것으로 접근하면 된다. 직사각형의 가로와 세로의 길이는 \(\frac{a+b+c}{4}\)를 올림, 내림한 값으로 정할 수 있다. BOJ 16681 - 등산 (G2) 더보기 보자마자 다익스트라 문제인건 알았는데, 무지성으로 다익스트라를 돌리면..

17940 - 지하철 (G2) 환승 비용을 10^6으로 잡고 다익스트라를 돌리면 된다. (N-1) * 1000 < 10^6이어서 가능하다. 2159 - 케익 배달 (G2) dp[n][k]를 n번째에서, k의 위치(상하좌우+원위치)에 있을 때의 최소 거리라고 정의하면, \(dp[i][j] = min(dp[i][j], f(i + 1, k, nx, ny) + |nx - x| + |ny - y|)\)라는 식이 나온다. 21757 - 나누기 (G3) 누적 합을 이용하면 된다. dp[n][k]를 n번째에서 나눈 구간의 개수가 k개일 때의 경우의 수라고 정의하면, \(0 \leq k \leq 3\)에서 해결할 수 있다. \(dp[i][j] = dp[i - 1][j]\)는 편안함을 위해 써두고, 추가적으로는 \(sum..

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

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://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://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\) 가 된다...

https://www.acmicpc.net/problem/16993 16993번: 연속합과 쿼리 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j : Ai, Ai+1, ..., Aj에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N) 수열의 인덱스는 1부터 시작 www.acmicpc.net 세그먼트 트리를 사용해서 풀면 된다. 왼쪽 끝점을 포함할 때의 구간합 최대 \(Seg_{ls}\) 오른쪽 끝점을 포함할 때의 구간합 최대 \(Seg_{rs}\) 어떤 구간에서의 구간합 최대 \(Seg_{ms}\) 구간의 합 \(Seg_{s}\) 자식 노드를 각각 \(L, R\)로 두면, \(Seg_{ls} = max(L_{ls}, L_{s} ..

https://www.acmicpc.net/problem/10848 10848번: 팔렘방의 다리 입력의 첫 줄에는 K와 N이 주어진다. 이후 N개의 줄에는 4개의 값 Pi, Si, Qi, Ti가 각각 주어진다. Pi와 Qi는 한글자 'A' 혹은 'B'이다. 0 ≤ Si, Ti ≤ 1, 000, 000, 000 사는 곳이나 사무실이 서로 다른 시민에 www.acmicpc.net 정말정말 좋은 문제이다. 일단, 한 도시에 집과 사무실이 모두 있는 경우는 없다고 가정하고, 다리의 길이를 무시해보자. \(k = 1\)일 때는, S와 T를 합쳐 정렬한 후, 중앙값이 다리의 좌표가 된다. \(k = 2\)일 때... \(f_i(x)\) 를 i번째 사람이 다리 x를 통해서 출근할 때의 거리라고 하면, \(f_i(x)..

https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net L~R까지의 합이 0이면 된다. 누적합과 세그트리를 사용하자 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 input = sys.stdin.readline INF = 10 ** 7 seg = [0 for _ in range(4040..