Cabbage Leaves Cabbage Leaves

전체 글

• 1283-D, *1800

  코드포스 2021. 9. 16. 00:53

  Problem - D - Codeforces codeforces.com 문제 $n(1 \leq n \leq 2\cdot 10^{5})$개의 나무가 수직선 위의 서로다른 $x_{i} \in \mathbb{Z}$에 있다 $m(1 \leq m \leq 2\cdot 10^{5})$명의 사람의 위치 $y_{i} \in \mathbb{Z}$는 다음 조건을 만족해야 한다 1. 나무가 있는 정수좌표에는 사람이 있으면 안된다 2. 한 좌표에는 두명 이상이 있으면 안된다 어떤 사람 $y_{i}$의 인접한 나무와의 거리를 $d_{i}$라 할때, $d_{i} = \overset{n}{\underset{j=1}{\text{min}}}|y_{i}-x_{j}|$ $d_{i}$의 합이 최소가 되도록 사람을 배치할 때의 $\mathr..

• 1654, Silver 3

  백준 2021. 9. 15. 01:00

  1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 $k(1 \leq k \leq 10^{4})$개의 랜선을 정수크기로 잘라 같은 길이의 $n(1\leq n \leq 10^{6})$개의 랜선을 사용한다 사용할 수 있는 가장 긴 랜선의 길이는? $O(k\cdot log\ n)$ 사용할 수 있는 랜선의 길이가 $hight$라고 가정하고 가능한지 불가능한지 판단한다. 각 랜선을 $hight$으로 나눴을 때 몫의 합이 $n$ 이상인지 판단하면 된다 $O(k)$ 이분탐색을 이용하여 $hi..

• boardcover, 하

  종만북 2021. 9. 4. 17:18

  https://algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 algospot.com 문제 . 과 # 으로 이루어진 $h \times w (1\leq h, w \leq 20)$ 행렬이 주어진다 3칸짜리 블록으로 . 칸을 채울 때, 경우의 수는? 풀이 완전탐색 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 3..

• picnic, 하

  종만북 2021. 9. 4. 14:40

  algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 algospot.com 문제 학생 수 $n(2\leq n \leq 10,\ 2\mid n)$와 $m(0\leq m \leq \binom{n}{2})$쌍의 친구관계가 주어진다 친구관계인 사람들끼리만 두명씩 짝지을 수 있는 경우의 수는? $O(\frac{\binom{n}{2}\binom{n-2}{2}\cdot \cdot \cdot\binom{2}{2}}{\frac{n}{2}!})$ $n=10$일 때, 완전탐색을 진행하여도 $9 \cdot 7 \cdot 5 \cdot 3 = 945$번만..

• 1560-A, *800

  코드포스 2021. 8. 30. 14:30

  Problem - 1560A - Codeforces codeforces.com 문제 1부터 다음 조건을 만족하는 수$x$를 나열할 때, $k(1\leq k \leq 1000)$번째 수는? $x$는 3의 배수가 아니며 일의자리수가 3이 아니다 $O(\frac{5}{3}k)\approx O(k)$ 1부터 하나하나 따질 때 시간복잡도 분석을 해보자 살구색 음영은 3의 배수인 수들이고 빨간색 빗금은 3의 배수가 아닌 수 중 일의자리수가 3인 수이다 위 수들은 주황색 점선을 기준으로 주기가 반복된다. 따라서 $$\frac{18}{30}\cdot \text{(last number)}\leq k$$ 1 2 3 4 5 6 7 8 like = [0] k = 1 while len(like)

• 11047, Silver 2

  백준 2021. 8. 19. 14:58

  11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 $n(1 \leq n \leq 10)$ 종류의 동전$c_{1},\ c_{2},\ \cdot \cdot \cdot,\ c_{n}(c_{i}\mid c_{i+1})$이 주어진다 이 동전들로 $k$원을 내기 위한 최소 개수를 구하라(돈을 못 내는 경우는 존재하지 않는다) $O(n)$ Greedy 단위가 큰 동전을 우선으로 가능한 많은 돈을 낸다 Claim

• 18242, silver 5

  백준 2021. 8. 18. 13:25

  18242번: 네모네모 시력검사 정사각형의 색칠하지 않은 한 변이 왼쪽, 오른쪽, 위쪽, 아래쪽일 때에 따라 각각 LEFT, RIGHT, UP, DOWN을 출력한다. www.acmicpc.net 문제 $n\times m(5\leq n,\ m \leq 100)$ 격자판에 한 변만 중심이 뚫린 직사각형이 있다. 뚤린 변은 어느쪽인가? $O(nm)$ 격자판을 위쪽부터 아래쪽으로, 왼쪽에서 아래쪽으로 탐색을 하면서 # 이 나올 때 좌표를 벡터에 저장한다 그러면 벡터의 제일 처음과 끝 원소는 아래 그림과 같다 ※ $x-y$ 좌표계가 아니라 행렬이라는 것에 주의할 것! 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 3..

• 1498-B, *1300

  코드포스 2021. 8. 16. 21:54

  Problem - 1498B - Codeforces codeforces.com 문제 높이가 1이고 너비가 2의 거듭제곱 형태$(w_{i} = 2^{k})$인 블록 $n(1\leq n \leq 10^{5})$개가 주어진다 높이가 1이고 너비가 $w$인 박스가 있을 때, 모든 블록을 담으려면 최소 몇 개의 박스가 필요한가? (단, $w \geq \mathrm{max(w_{i})}$ 풀이1 Greedy 너비가 큰 블록부터 상자에 넣는다. 블록이 들어간 상자들 중 남는 자리가 있으면 그 곳에 채워넣고, 없으면 새로운 상자에 블록을 넣는다 Claim 1 $w_{i}$가 2의 거듭제곱 꼴이고 $w_{1}$ 부터 $w_{n}$이 증가할때 $$\begin{aligned} &w_{1}+w_{2}+\cdot \cdot \..