[SISS/C언어 스터디] 2학기 7주차 스터디

2학기 7주차 스터디

백준 제출 내역 화면 캡쳐

자율 2문제를 풀어서 제출하면 됩니다.

언어는 C언어만 가능합니다.

​레벨 제한사항: Silver 5 이상

 

10816

---

• 이분 탐색 → 주어진 값이 배열에 몇 번 나타나는지 계산

// 10816

#include <stdio.h>
#include <stdlib.h>

// qsort에서 사용할 비교 함수
int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

// target 이상의 값이 처음 나오는 인덱스를 반환
int left_side(int arr[], int size, int target)
{
    int left = 0, right = size;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] >= target)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}

// target 초과의 값이 처음 나오는 인덱스를 반환
int right_side(int arr[], int size, int target)
{
    int left = 0, right = size;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (arr[mid] > target)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}

int main()
{
    int N, M, n;

    // N 입력
    scanf("%d", &N);
    int v[N];

    // N개의 숫자 입력
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &v[i]);
    }

    // 배열 정렬
    qsort(v, N, sizeof(int), compare);

    // M 입력
    scanf("%d", &M);

    // M개의 숫자 입력
    for (int i = 0; i < M; i++)
    {
        scanf("%d", &n);
        int count = right_side(v, N, n) - left_side(v, N, n); // 해당 숫자가 나타나는 횟수 계산
        printf("%d ", count);
    }

    return 0;
}

 

1358

---

• 기하학 → 링크를 기본 도형으로 쪼개어 풀이

// 1358

#include <stdio.h>
#include <math.h>

// 점이 링크 안에 있는지 확인
int is_inside(int W, int H, int X, int Y, int a, int b)
{
    // 직사각형 내부 확인
    if (X <= a && a <= X + W && Y <= b && b <= Y + H)
    {
        return 1;
    }

    // 왼쪽 원의 중심 좌표
    double left_center_x = X;
    double left_center_y = Y + H / 2.0;

    // 왼쪽 원 내부 확인
    if ((a - left_center_x) * (a - left_center_x) +
            (b - left_center_y) * (b - left_center_y) <=
        (H / 2.0) * (H / 2.0))
    {
        return 1;
    }

    // 오른쪽 원의 중심 좌표
    double right_center_x = X + W;
    double right_center_y = Y + H / 2.0;

    // 오른쪽 원 내부 확인
    if ((a - right_center_x) * (a - right_center_x) +
            (b - right_center_y) * (b - right_center_y) <=
        (H / 2.0) * (H / 2.0))
    {
        return 1;
    }

    // 내부에 없으면 0 반환
    return 0;
}

int main()
{
    int W, H, X, Y, P;
    int result = 0;

    // W, H, X, Y, P 입력
    scanf("%d %d %d %d %d", &W, &H, &X, &Y, &P);

    // P개의 점에 대해
    for (int i = 0; i < P; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);

        // 점이 링크 안에 있으면 result 증가
        result += is_inside(W, H, X, Y, a, b);
    }

    // 출력
    printf("%d\n", result);

    return 0;
}