넘치게 채우기

https://www.acmicpc.net/problem/1477BOJ - 휴게소 세우기문제 유형: 이진 탐색, 매개변수 탐색(parametric search)문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 ..

https://www.acmicpc.net/problem/1114BOJ - 통나무 자르기문제 유형: 이진 탐색, 매개 변수 탐색문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제벌목꾼 백은진은 나무를 종이 공장에 옮겨야 한다. 하지만, 통나무의 길이가 너무 길어서 트럭에 들어가지 않으므로, 여러개의 조각으로 나누려고 한다.통나무의 길이는 L이고, K개의 위치에서만 자를 수 있다. 통나무를 자를 수 있는 위치가 주어진다. 이 위치는 통나무의 가장 왼쪽에서부터 떨어진 거리이다. 통나무를 자를 수 있는 횟수는 최대 C번이다.통나무의 가장 긴 조각을 작게 만들고, 그 길이를 구해보자. 입력첫째 줄에 세 정수 L, K, C가 주어진다. 둘째 줄에는 통나무를 자를 수 있는 위치가 주어진다. 출력..

https://codeforces.com/contest/2064/problem/DCodeforces Round 1005(Div. 2) - D. Eating문제 유형: 그리디, 비트마스킹, 이진 탐색시간 제한: 5초메모리 제한: 512MB 문제There are n">n slimes on a line, the i">i-th of which has weight wi">wi. Slime i">i is able to eat another slime j">j if wi≥wj">wi≥wj; afterwards, slime j">j disappears and the weight of slime i">i becomes wi⊕wj">wi⊕wj.The King of Slimes wants to ru..

https://www.acmicpc.net/problem/1300BOJ - K번째 수문제 유형: 매개변수 탐색(parametric search), 이진 탐색, 행렬문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.배열 A와 B의 인덱스는 1부터 시작한다. 입력첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다. 출력B[k]를 출력한다. 풀이n이 정해져 있고 2D배열 A에..

https://www.acmicpc.net/problem/2110BOJ - 공유기 설치문제 유형: 이진 탐색, 매개 변수 탐색(parametric search)문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는..

https://www.acmicpc.net/problem/1654BOJ - 랜선 자르기문제 유형: 이진 탐색, 매개 변수 탐색(parametric search)문제 난이도: Silver II시간 제한: 2초메모리 제한: 128MB 문제집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선..

https://www.acmicpc.net/problem/32984BOJ - 겨울이 좋아문제 유형: 이진탐색, 매개변수 탐색문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제정우는 겨울을 너무 좋아한다. 하지만 아쉽게도 지금은 가을이다. 정우가 사는 도시에는 N그루의 나무가 있고 A번째 나무에는 A_i개의 나뭇잎이 붙어있다. i번째 나무의 나뭇잎은 하루에 Bi개씩 떨어지며, Bi개보다 적게 남아있을 경우에는 전부 떨어진다. 정우는 N그루의 나무에 있는 모든 나뭇잎이 떨어진 날부터를 겨울이라고 부른다.정우는 특별한 능력을 가지고 있는데, 매일 하나의 나무를 선택해서 그날에 나뭇잎이 2배로 떨어지게 만들 수 있다. 다시 말해서 정우가 i번째 나무를 선택해서 능력을 사용하면 그날 그 ..

https://www.acmicpc.net/problem/16566BOJ - 카드 게임문제 유형: 분리 집합, 이진 탐색, 유니온-파인드문제 난이도: Platinum V시간 제한: 1.2초메모리 제한: 512MB 문제철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번..

https://www.acmicpc.net/problem/2887BOJ - 행성 터널문제 유형: MST(최소 신장 트리), 최단 경로, 그래프, 정렬, 이진 탐색문제 난이도: Platinum V시간 제한: 1초메모리 제한: 128MB 문제때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모..

https://www.acmicpc.net/problem/7453BOJ - 합이 0인 네 정수문제 유형: 이진탐색, 해시, 투포인터, MITM(Meet-In-The-Middle)문제 난이도: Gold II시간 제한: 12초메모리 제한: 1024MB 문제정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 2^28이다. 출력합이 0이 되는 쌍의 개수를 출력한다. 풀이브루트 포스는 n^4의 ..