[BOJ_7795] 먹을 것인가 먹힐 것인가

 

📌 문제 링크: https://www.acmicpc.net/problem/7795

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

 

✅ 내 풀이(Success) :

 

🧐 Review:

 파이썬에서는 인덱스가 0부터 시작하므로 A가 잡아먹을 수 있는 쌍의 수(count)를 셀 때, 인덱스 값인 end에 1을 더해준다.

 

🚩 Idea:

 - 생명체 A와 B의 배열의 최대 크기가 모두 20,000이다.

 - A배열의 모든 원소에 대해 B원소를 잡아먹을 수 있는지 이중 for문으로 비교하는 것이 가장 쉬운 방법이지만 입력 값의 크기로 인해 O(n^2)의 알고리즘은 시간 초과가 날 것이다.

 - 그렇다면 시간복잡도를 낮추기 위한 방법으로 이분 탐색(binary search)을 고려해보면 좋을 것 같다.