본문 바로가기

이분탐색

(1)

[Java] 백준 31091 - 거짓말 https://www.acmicpc.net/problem/31091 풀이 예를들어, N = 5명이고, 각자 다음과 같이 주장하고 있다 [ 1, 4, 3, 5, 2 ] 이 상황에서 거짓말한 사람의 수가 3명이 가능한지 확인하고 싶다면 1. 배열을 정렬한다 : [ 1, 4, 3, 5, 2 ] ==> [ 1, 2, 3, 4, 5 ] 2. (사람의 수 − 3보다 최초로 큰 값의 인덱스) = 5 - 3 = 2 3. 2 != 3 ∴ 거짓말한 사람이 3명이 될 수 없다. 이런 식으로 가능한 거짓말쟁이의 수를 0부터 N까지 돌려보고, 이분탐색(upper bound)로 실제 거짓말한 인원을 확인하고 비교해주면 된다. 다만 음수와 양수는 따로 다른 배열에 저장해서 돌려야하고, 음수 배열에서 이분탐색 돌릴 때 목표값을 음수..

이전 1 다음

티스토리툴바