6-A_ 2792 보석상자 강의 질문

작성한 질문수 25

1

효민님 감사합니다! 문제 자체를 이해하기 도 어려웠는데, 강의를 보고도, 형광팬 문제를 보고도 제대로 이해가 안되었었는데, 효민님의 그림을 보고 정리가 안되던 부분이 정리가 되었네요. 질문자분께 감사하다는 말씀 남기고 싶습니다.

0

안녕하세요 효민님 ㅎㅎ

그림 너무 잘그리시네요.. ㅎㅎ 항상 그림이 너무 이쁘네요 ㅎㅎ

반대로 생각하시는 것 같아요.

질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다

이 질투심을 최소화 하는 것인데요.

if 질투심 == 2 : 학생수는 6명이 되어서 만족합니다. 다만 그렇다고 2가 답일까요?

아닙니다. 사실 저게 1개가 남게 되면 학생수가 5명이기 때문에 한명은 3, 질투심은 3이 되게 됩니다.

우리는 질투심이 ~~ 일 때 학생수를 만족하는지만 확인하면 됩니다.

만약 만족했을 때 그 값이 너무 크다면 줄이고, 작다면 좀 더 늘려서 적당한 값을 찾아나가는 것이죠.

자세히 얘기하자면,

나눠버린 몫 cnt가 학생수 n ==> 충족 / 질투심을 최소화해야 하기 때문에 나누는 것을 더 줄여야 합니다.

나눠버린 몫 cnt가 학생수 n 미만 ==> 불충족 / 나누는 것을 좀 더 줄여야 합니다.

나눠버린 몫 cnt가 학생수 n 보다 큼 ==> 충족 / 좀 더 질투심을 늘려야 함 -> 학생수가 크다는 것은 그만큼의 나머지를 한명의 학생이 가져간다는 의미.

이러한 부분을 코드로 나타내면.

bool check(ll mid){ 
...
    return n >= num; 
}

    while(lo <= hi){
        mid = (lo + hi) / 2; 
        if(check(mid)){ 
            ret = min(ret, mid); 
            hi = mid - 1; 
        }else lo = mid + 1; 
    }

이렇게 되는 것이죠.

감사합니다.