넘치게 채우기

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의 ..

https://www.acmicpc.net/problem/12015BOJ - 가장 긴 증가하는 부분 수열 2문제 유형: LIS(Longest Increasing Subsequence), 다이나믹 프로그래밍, 이진 탐색난이도: Gold II시간 제한: 1초메모리 제한: 512MB 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,00..

https://www.acmicpc.net/problem/14003BOJ - 가장 긴 증가하는 부분 수열 5문제 유형: LIS(Longest Increasing Subsequence), 다이나믹 프로그래밍, 이진 탐색문제 난이도: Platinum V시간 제한: 3초메모리 제한: 512MB 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,..

https://www.acmicpc.net/problem/2143BOJ - 두 배열의 합문제 유형: 이진 탐색, 부분합, 정렬문제 난이도: Gold III시간 제한: 2초메모리 제한: 64MB 문제한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우..

https://leetcode.com/problems/find-building-where-alice-and-bob-can-meet/description/leetcode - Find Building Where Alice and Bob Can Meet문제 유형: 이진 탐색, 모노토닉 스택문제 난이도: Hard 문제You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the ith building.If a person is in building i, they can move to any other building j if and only if i  and heights[i] Yo..

https://leetcode.com/problems/special-array-ii/description/leetcode - Special Array II문제 유형: 이진 탐색문제 난이도: Medium 문제An array is considered special if every pair of its adjacent elements contains two numbers with different parity.You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [fromi, toi] your task is to check that subarray nums[fromi..toi] is specia..

https://leetcode.com/problems/two-best-non-overlapping-events/description/leetcode - Two Best Non-Overlapping Events문제 유형: 이진 탐색문제 난이도: Medium 문제You are given a 0-indexed 2D integer array of events where events[i] = [startTimei, endTimei, valuei]. The ith event starts at startTimei and ends at endTimei, and if you attend this event, you will receive a value of valuei. You can choose at most two ..