BOJ 7795 먹을 것인가 먹힐 것인가

2020. 10. 11. 02:40·알고리즘/BOJ

www.acmicpc.net/problem/7795

 

7795번: 먹을 것인가 먹힐 것인가

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 ��

www.acmicpc.net

 

집합 A와 B가 주어지면 A의 각 원소를 B에서 순회하면서 그 원소보다 작은 것들이 몇 개 존재하는지를 알아내는 문제다.

처음엔 투 포인터로 접근했는데 갈수록 막히는 것 같아서 이분탐색으로 해결했다.

 

  • 집합 A와 B를 입력받고 두 집합을 정렬한다
  • A집합의 원소를 B집합에서 순회하면서 각 원소보다 큰 원소들이 몇개 있는지 카운트한다
  • cnt 변수에 더해준다

매우 간단한 접근이였다.

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

int a[20001], b[20001], tc, n, m, cnt;

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

	cin >> tc;
	while (tc--) {
		cin >> n >> m;
		for (int i = 0; i < n; i++) cin >> a[i];
		for (int i = 0; i < m; i++) cin >> b[i];
		sort(a, a + n);
		sort(b, b + m);

		cnt = 0;
		for (int i = 0; i < n; i++) {
			int it = lower_bound(b, b + m, a[i]) - b;
			cnt += it;
		}
		cout << cnt << '\n';
	}

	return 0;
}


 

int it = lower_bound(b, b + m, a[i]) - b;

 

이 코드를 통해 a [i]의 원소가 B집합의 몇 번째 수에 있는지 알 수 있다.

만약 a [i]보다 큰 원소가 B집합에 없다면 마지막 인덱스를 반환할 것이다.

이후에 cnt에 추가해주면 된다.

'알고리즘 > BOJ' 카테고리의 다른 글

BOJ 1976 여행 가자  (0) 2020.10.15
BOJ 2470 두 용액  (0) 2020.10.11
BOJ 1806 부분합  (0) 2020.10.10
BOJ 13414 수강 신청  (0) 2020.10.07
BOJ 1059 수2  (0) 2020.10.07
'알고리즘/BOJ' 카테고리의 다른 글
  • BOJ 1976 여행 가자
  • BOJ 2470 두 용액
  • BOJ 1806 부분합
  • BOJ 13414 수강 신청
khyu2
khyu2
  • khyu2
    dev log
    khyu2
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘
        • BOJ
        • Programmers
        • Algorithm
        • SWEA
      • 개발
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    소수
    dfs
    BFS
    dp
    MST
    다익스트라
    분할 정복
    코딩테스트 연습
    프로그래머스
    조합
    구현
    완전 탐색
    완전탐색
    행렬 제곱
    BOJ
    유니온 파인드
    피사노 주기
    피보나치 수
    크루스칼
    이분 탐색
    GREEDY
    SWEA
    시뮬레이션
    팰린드롬
    큐
    우선순위 큐
    트리
    알고리즘
    이분탐색
    냅색
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
khyu2
BOJ 7795 먹을 것인가 먹힐 것인가
상단으로

티스토리툴바