0x13강 - 이분탐색

[Jinsun-Lee]

리드미

• 나무자르기 개념 추가 설명
• 바킹독 개념
• 0x13강 - 이분탐색
• 0x0C강 - 이분탐색_구버전

[Jinsun-Lee]

추가 풀이한 문제 (리드미에 없음)

• 10815. 숫자 카드: 수찾기랑 똑같음 개쉬움
• 2295. 세 수의 합
• ⭐1253. 좋다: 이분탐색&투포인터
• ⭐2003. 수들의 합 2: 정렬해 버리면 안 되지 구간합인데&투포인터

• ⭐2776. 암기왕: 문제 자체는 쉬운데, vector → unordered_set → set 비교에 좋음

[Jinsun-Lee]

좋다

#include <iostream>
#include <algorithm>
using namespace std;

int A[2'000];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; ++i) cin >> A[i];

	if (n <= 2) { // 누락 주의
		cout << 0;
		return 0;
	}

	sort(A, A+n);

	int cnt = 0;
	for (int k = 0; k < n; ++k) {
		int st = 0, en = n - 1; // 투포인터

		while (st < en) { // 등호 주의
			if (st == k) { ++st; continue; }
			if (en == k) { --en; continue; }

			long long sum = A[st] + A[en];
			
			if (sum == A[k]) {
				++cnt;
				break;
			}

			if (sum < A[k]) ++st;
			else --en;
		}
	}

	cout << cnt;
	return 0;
}

[Jinsun-Lee]

수들의 합 2

#include <iostream>
#include <algorithm>
using namespace std;

int A[10'001];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;

	for (int i = 0; i < n; ++i) cin >> A[i];

	long long sum = 0;
	int st = 0, en = 0, cnt = 0;
	
	while (1) { // 후위 증가여야만 해
		if (sum >=m) sum -= A[st++]; // 합이 크면 왼쪽 줄이기
		else if (en == n) break; // 합이 크면 왼쪽 줄이기
		else sum += A[en++]; // 합이 작으면 오른쪽 늘리기

		if (sum == m) ++cnt; // m을 만들 수 있는 구간 설정이 가능함
	}

	cout << cnt;
	return 0;
}

[Jinsun-Lee]

휴게소 세우기

#include <iostream>
#include <algorithm>
using namespace std;

int N, M, L;
int A[1'002];

bool check(const int mid) { // 휴게소가 없는 구간의 최댓값이 mid 이하가 가능한가?
	int cnt = 0;
    int prev = 0; // 시작점

	for (int i = 0; i < N; ++i) {
		int dist = A[i] - prev;
		cnt += (dist - 1) / mid; // 이렇게 하면 이미 휴게소 있는 경우 처리됨
        prev = A[i];
    }
    
    // 마지막 구간 (L - 마지막 휴게소)
    cnt += (L - prev - 1) / mid;
    return cnt <= M; // 지을 수 있는 휴게소가 m개보다 작다면 mid 줄여서 m개만큼 짓게
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> L;

	for (int i = 0; i < N; ++i) cin >> A[i];
	sort(A, A + N);

	int st = 1, en = L-1, mid, ans = 0;
	while (st <= en) {
		mid = st / 2 + en / 2 + (1&st&en);

		if (check(mid)) { // M개보다 적어서 간격 줄이기
			ans = mid;
			en = mid - 1;
		}
		else st = mid + 1; // 구간이 너무 좁음, 늘려야 함
	}
	cout << ans;
	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M, L, x; cin >> N >> M >> L;

    v.push_back(0);
	for (int i = 0; i < N; i++) {
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	v.push_back(L);
    
    int st = 1, en = L, mid;
	while (st <= en) {
		mid = (st + en) / 2;
            
		int cnt = 0;

		for (int i = 1; i < v.size(); i++) {
			int dist = v[i] - v[i - 1];
			cnt += dist / mid; // 두 휴게소 사이에 지을 수 있는 휴게소의 수

			if (dist % mid == 0) --cnt; //이미 휴게소가 있을 경우에는 못 지어서
		}

		if (cnt > M) st = mid + 1; // 개수가 M개보다 많아서 간격 넓힘
		else en = mid - 1; // M개보다 적어서 간격 줄이기
	}

	cout << st;
	return 0;
}

[Jinsun-Lee]

과자 나눠주기

#include <iostream>
#include <algorithm>
using namespace std;

int N, M, arr[1'000'000]; // 조카 M, 과자 N

bool check(const int mid) { // mid의 길이의 막대과자가 조카M명보다 크거나 같아야 true
	int cnt = 0;
	for (int i = 0; i < N; ++i) {
		//if (arr[i] >= mid) ++;
		cnt += arr[i] / mid; // mid 길이로 나눠줄 수 있는 조카의 수
	}
	return cnt >= M;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> M >> N; 
	for (int i = 0; i < N; ++i) cin >> arr[i]; 
	sort(arr, arr + N);

	int st = 1, en = arr[N-1], ans = 0, mid; // st, en 범위 주의
	while (st <= en) {
		mid = st / 2 + en / 2 + (1&st&en);
		if (check(mid)) {
			ans = mid;
			st = mid + 1;
		}
		else en = mid - 1;
	}
	
	cout << ans;
	return 0;
}

[Jinsun-Lee]

2512. 예산

[Jinsun-Lee]

[Jinsun-Lee]

멀티버스 Ⅱ
용액
용액 합성하기
공유기 설치
합이 0
두 배열의 합
세 용액
합이 0인 네 정수
가장 긴 증가하는 부분 수열 2

[Jinsun-Lee]

[Jinsun-Lee]

암기왕

벡터가 메모리랑 시간 압도적 → unordered_set이 메모리 엄청 쓰고 시간은 좀 느림 → set

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int T; cin >> T;
    while (T--) {
        int N; cin >> N; // 1. 변수를 반복문 안에 선언하고
        
        vector<int> note1(N);
        for (int i = 0; i < N; ++i) cin >> note1[i];
        sort(note1.begin(), note1.end());

        int M; cin >> M;
        for (int i = 0; i < M; ++i) {
            int x; cin >> x;
            if (binary_search(note1.begin(), note1.end(), x)) cout << "1\n";
            else cout << "0\n"; // 2. if-else로 출력하는 게 훨 빨라
        }
    }
    return 0;
}

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int T; cin >> T;
    while (T--) {
        int N; cin >> N;

        unordered_set<int> note1;
        note1.reserve(N); // 메모리 확보
        
        for (int i = 0; i < N; ++i) {
            int x; cin >> x;
            note1.insert(x);
        }

        int M; cin >> M;
        for (int i = 0; i < M; ++i) {
            int x; cin >> x;
            if (note1.find(x) != note1.end()) cout << "1\n";
            else cout << "0\n";
        }
    }
    return 0;
}

#include <iostream>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        
        set<int> note1; // 크기는 지정 불가
        for (int i = 0; i < N; ++i) {
            int x; cin >> x;
            note1.insert(x);
        }

        int M; cin >> M;
        for (int i = 0; i < M; ++i) {
            int x; cin >> x;
            if (note1.find(x) != note1.end()) cout << "1\n";
            else cout << "0\n"; // 3. set에서는 find를 써!
        }
    }
    return 0;
}

[Jinsun-Lee]

보석 상자

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long; // 킥...

int sCnt, cCnt; // 학생의 수, 색상의 수
vector<int> dia; // 각 색상 별 몇 개?

bool check(const ll mid) {
    // mid는 한 학생이 받을 수 있는 최대 보석의 개수 = 질투심
    ll cnt = 0; // 이 mid로 모든 보석을 나누기 위해 필요한 학생의 수
    for (const int a : dia) {
        cnt += (a / mid);
        if (a % mid != 0) ++cnt;
    }
    return cnt <= sCnt; // 필요한 학생 수 <= 실제 학생 수
    // 학생이 충분히 많아 = 더 작은 질투심으로 탐색 가능 = mid 줄여보자
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> sCnt >> cCnt;
    dia.resize(cCnt);

    ll st = 1, en = 0;

    for (int i = 0; i < cCnt; ++i) {
        cin >> dia[i];
        if (en < dia[i]) en = dia[i]; // 킥
    }

    ll ans = en; // 킥
    
    while (st <= en) {
        ll mid = (st + en) / 2;
        
        if (check(mid)) {
            ans = mid;
            en = mid - 1; // 더 작게 시도
        }
        else st = mid + 1; // mid가 작음, 늘려 = 한 학생이 더 많이 받게
    }
    
    cout << ans;
    return 0;
}