MZ 개발자

이 문제는 얼마전 포스팅했던 BOJ 1654 랜선 자르기 문제와 100%일치하는 문제이다. 핵심은 적절한 나무 길이를 구하기 위해 이진 탐색을 이용해야하는 것이다. https://devconf.tistory.com/65 BOJ 1654 랜선 자르기 이 문제는 K개의 랜선이 주어지고 이를 이용하여 N 개(이상)의 랜선을 만든는데 랜선의 길이를 가장 길게 만들때 그 랜선의 길이를 구하는 문제이다. 시작 아이디어는 주어진 K개의 랜선으로 N개( devconf.tistory.com #include #include #include #include using namespace std; typedef long long ll; int n, m; vector len; ll result; bool cmp(ll a, ll ..

이 문제는 N개의 카드중에서 M개의 카드 숫자가 몇개 있는지 찾는 문제이다. 단순한게 브루트포스 방법 O(n^2)으로 문제를 해결하려고 시도한다면 N = 500000, M = 500000 이므로 시간초과가 발생한다. 따라서 특정 숫자가 어디에 있는지 빠르게 탐색하기 위해 이진탐색으로 접근해야 한다. 이진탐색을 하기 위해서는 우선 상근이의 숫자 카드 N이 오름 차순으로 정렬이 되어있어야 한다. 이때 핵심은 중복된 숫자 카드를 어떻게 표현할 것인가 이다. 오름 차순 정렬 후 앞쪽부터 순회하면서 중복된 숫자를 pair 로 변환 시켜준다. 예를들어 N이 -10, -10, 1, 3, 5, 10, 10, 10 일경우 {-10,2}, {1,1}, {3,1}, {5,1}, {10,3} 과 같은 형태로 변환을 시켜준다...

이 문제의 핵심은 모든 통나무 조각 길이보다 큰 경우를 만족하는 적절한 길이의 통나무를 구하는 문제이다. 예를들어 L =9, K=2, C=1 일 경우 나올수 있는 통나무 조각은 4,1,4이다. 이때 모든 통나무 조각 길이 보다 긴 적절한 길이의 통나무를 구해야한다. 우리가 생각해야하는 조건은 두가지이다. 1. 모든 잘린 통나무 조각은 적절히 자를수 있는 최대 길이(mid)로 모두 자를 수 있어야 한다. 2. 자를수 있는 횟수를 초과 하면 안된다. 이를 바탕으로 풀이를 다음과 같이 생각해볼 수 있다. 1. 만약 잘린 통나무 누적 길이가 mid보다 커지는 순간까지 cut을 하지 않고, 커지는 순간 cnt을 증가시켜준다. 2. 이후 마지막으로 누적한 통나무의 길이가 mid 보다 클경우 위의 조건 1을 만족하지..