BOJ 10815 - 숫자카드

whipbaek·2021년 9월 20일
0

BOJ

목록 보기
8/15

Problem
https://www.acmicpc.net/problem/10815

소유하는 카드를 입력받은후에

입력으로 들어오는 카드를 가지고 있는지 검사하여 가지고 있으면 1, 아니면 0을 출력하는 프로그램을 작성하라

Solution

단순한 이분탐색 문제이다.

이분탐색은 정렬되어있어야하기에 입력을 받은후 정렬을 한다음, 이분탐색으로 각각의 케이스에 대한 답을 도출해준다.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;

    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    cin >> m;

    while (m--) {
        int goal;
        cin >> goal;

        int left = 0;
        int right = n - 1;
        bool state = false;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (a[mid] == goal) {
                state = true;
                break;
            }

            if (a[mid] > goal) {
                right = mid - 1;
            }

            else {
                left = mid + 1;
            }
        }

        if (state) cout << 1 << ' ';
        else cout << 0 << ' ';
    }

    return 0;
}

참고 : https://code.plus/course/43 , 분할 정복

profile
코딩 및 CS에 관하여 공부합니다.

0개의 댓글