백준
-
2170, Gold 5백준 2021. 10. 3. 00:29
2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 문제 $n(1\leq n \leq 10^{6})$번 수직선 위의 구간 $[x, y], -10^{9}\leq x < y \leq 10^{9}$에 선분을 긋는다 그려진 선들의 길이의 합? $O(nlog\ n)$ 선분들을 정렬한 후 $O(nlog\ n)$ 선분들이 하나의 연속된 그룹(두 선분 사이에 빈틈이 없으면 연속이라 하자)인지 아닌지를 판단한다 $O(n)$ i) $s \leq r$이면 연속 ii) $r < s$이면 불연속 c++ 1 ..
-
16768, Gold 4백준 2021. 9. 21. 16:44
16768번: Mooyo Mooyo In the example above, if $K = 3$, then there is a connected region of size at least $K$ with color 1 and also one with color 2. Once these are simultaneously removed, the board temporarily looks like this: 0000000000 0000000300 0054000300 1054500030 220000 www.acmicpc.net 문제 같은 숫자가 $k$개 이상 인접하면 사라지고 아래로 내려온다. 최종 모습은? 풀이 ※ 마킹한 1은 미리 0으로 바꾸지 않는다(변화는 항상 마지막에) 화살표를 따라가다가 0을 만나면 열..
-
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..
-
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..
-
16237, bronze 1백준 2021. 8. 16. 16:08
16237번: 이삿짐센터 첫째 줄에 A, B, C, D, E가 주어진다. (0 ≤ A, B, C, D, E ≤ 1,000) www.acmicpc.net 문제 1kg, 2kg, ..., 5kg 인 물건이 각각 $0\leq a,\ b,\ c,\ d,\ e \leq 1000$개 있다 물건들을 모두 옮기는데 최대 5kg 까지 담을 수 있는 바구니를 사용할 때 최소 몇 개가 필요한가? $O(\mathrm{stuff_{max}}log\ \mathrm{stuff_{max}})$ Greedy 가장 무거운 물건을 우선으로 가방에 담는다 무거운 물건을 우선으로, 이미 물건이 담긴 가방에 담을 수 있다면 담고, 없다면 새로운 가방에 물건을 넣는다 Claim 최적 알고리즘을 사용하여 가방에 넣은 물건들의 자리를 사용한 가방의..
-
11000백준 2021. 8. 3. 21:44
11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 $n(1 \leq n \leq 2\cdot 10^{5}$개의 수업을 가능하게 하기 위한 최소 강의실의 개수? 강의시간은 $[s,\ e)$ 이다(강의시간에 시각 e 는 포함하지 않는다) $O(nlog\ n)$ 빨리 시작하는 순서로 고려한다 기존 강의실에 배정할 수 있으면 배정하고 못한다면 새로운 강의실을 만든다 위의 알고리즘을 진행하면서 강의실을 가장 많이 사용할 때의 강의실 수가 최적해이다 위 그림에서 실선 t 와 만나는 강의의 개수를 $U(t)$라고 하자 Claim 준 알고리즘의 해는 (수업이 최대로 겹..
-
1931백준 2021. 8. 3. 19:37
1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 회의시간이 $n(1\leq n \leq 10^{5})$개 주어질 때 최대로 진행할 수 있는 회의의 개수? $O(nlog\ n)$ 남은 회의 중 가장 빨리 끝나는 회의를 우선으로 배정한다 위 알고리즘으로 선택한 회의를 $S$, 최적해를 $O$라 하자 이때 각 집합은 회의가 빨리끝나는 순으로 indexing 되어있다 $$\begin{align*} &S:= \left \{ p_{1},\ p_{2},\cdot \cdot \cdot, p_{k} \right \}\\ &O:= \left \{ q_{1},\ q_{2},\cdot \cdot \cdot, q_{l} \right \} \e..