백준 19599 이진 삼진 탐색 놀이 [c++]

23 Jun 2022 in Develop / Solving

cpp

문제 분석

• 숫자 하나가 주어진다. 이 숫자는 배열의 크기이고, 배열에는 [0 ~ N-1]까지가 담긴다.
• 이진 삼진 탐색을 사용할 때,
• 답을 찾을 때 까지 참조하는 수를 구하고,
• 이진, 삼진 탐색 중 어느것이 더 수를 많이 참조하는지 구하여라

입력조건

배열의 크기 N

풀이과정

• 주어진 이진, 삼진 탐색 코드를 이용해서 이진, 삼진 탐색 코드를 작성.
• 참조하는 수가 하나 늘 때 마다 count를 더해가며, 이를 return함.

전체 코드

#include <iostream>

using namespace std;

int binary_search(int count, int value, int left, int right) {
    int mid = (left + right) / 2;

    if(mid == value) return count;
    else if(value < mid)
        return binary_search(count + 1, value, left, mid-1);
    else
        return binary_search(count + 1, value, mid+1, right);
}

int ternary_search(int count, int value, int left, int right) {   
    int left_third = left + (right - left) / 3;
    int right_third = right - (right - left) / 3;
    
    // 하나도 참조하지 않음.
    if(left_third == value) return count;
    // left_third만 참조함.
    else if(right_third == value) return count + 1;
    // left_third, right_third 다 참조함.
    else if(value < left_third)  return ternary_search(count + 2, value, left, left_third -1);
    else if(value < right_third) return ternary_search(count + 2, value, left_third +1, right_third -1);
    else                         return ternary_search(count + 2, value, right_third +1, right);
}

int main() {
    int n;
    cin >> n;
    
    int a = 0;
    int b = 0;
    int c = 0;
    for(int i = 0; i < n; i++){
        int bc = binary_search(0, i, 0, n-1);
        int tc = ternary_search(0, i, 0, n-1);

        cout << bc << " " << tc << endl;
        if(bc < tc) a++;
        else if(bc == tc) b++;
        else c++;
    }
    
    printf("%d\n%d\n%d", a, b, c);
}