(JAVA) 백준 2792번 : 보석 상자 --- [이진탐색]

https://www.acmicpc.net/problem/2792

2792번: 보석 상자

 

 

이분탐색 문제이다.

 

도저히 고민하다가 못풀겠어서

 

풀이 방법을 살짝(많이) 보고 이해한 다음 해결했다..

 

 

이분탐색 어렵다.

 

계속 관련 유형 문제들을 풀어봐야겠다.

 

 

 

 

핵심은 문제에 있다.

 

 

  1.  모든 보석을 N명의 학생들에게 나눠줘야 한다. 모든 보석이다. 하나라도 남으면 안된다.

 

 

  2.  보석을 받지 못하는 학생이 있어도 된다. 즉, 모든 보석을 나눠줘야 하지만 한명당 꼭 하나 이상씩 나눠줄 필요는 없다.

    한명한테 올인해도 된다. (이러면 질투심이 치솟는다.)

 

 

  3.  학생은 항상 같은 색상의 보석만 가져간다. 종류별로 하나씩(ex. 다이아, 루비, 사파이어 등) 가져갈 수 없다.

    무조건 한 종류의 보석만 가능하다. 다이아만 챙겨가야한다.

 

 

  4.  질투심의 최솟값을 구하는 문제.  질투심이란, 모든 학생들 중 보석을 가장 많이 가져간 학생의 보석 갯수 이다. 

    그렇기 때문에, 최대한 큰 오차없이 나눠줘야 한다.

 

 

 

이분탐색(Binary Search)을 사용해보자.

 

 

이분탐색이란, 정렬된 배열에서 중간 값과 찾을 값을 비교해서 크면 위 배열, 작으면 아래 배열만 탐색해나가는 알고리즘이다.

 

그렇기 때문에, log(n) 의 시간복잡도를 가진다.

 

 

이 문제는 1초이기 때문에 단순 탐색으로는 시간초과가 발생할 것이다.

그래서 이분탐색을 사용한다.

 

 

 

 

 

 

 

자, 그럼 여기서는 어떻게 이진탐색을 적용시킬까?

 

 

정렬된 배열 : 질투심의 범위(최소 범위 : 1, 최대 범위 : 여러 종류의 보석들 중 가장 개수가 많은 보석의 총 개수)

 

찾을 값 : 해당 질투심(중간 값) 을 만족하기 위해 필요한 최소 인원 수

    -  최소 인원 수 를 구하는 방법 : (해당 질투심 / 각 종류 별 보석의 개수) + 1  

    *** +1 을 하는 이유는 나머지 보석들을 막내 한 명이 짬처리해줘야 하므로.

    *** 그래서 만약 해당 질투심 % 각 종류 별 보석의 개수 가 0 이 나올 경우(나누어떨어짐) +1을 하지 않는다.

 

 

 

 

그래서 각 보석 종류 별로 최소 인원 수를 다 더했을 때,

 

 

N 보다 같거나 작으면 이 값을 저장하고, 아래 배열을 탐색한다.

*** 질투심을 더 낮출 수 있을 지 도전!

*** 남은 학생들에게는 안줘도 되니까 질투심이 성립한다.

 

 

N 보다 크면 위 배열을 탐색한다.

*** 절대 해당 질투심을 만족할 수 없음.

*** 질투심을 높여보자.

 

 

 

 

이렇게 하면 문제 해결!

 

감사합니다.

 

 

소스코드

---