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

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

6-A

해결된 질문

작성

296

안녕하세요 큰돌님 강의를 듣다가 질문이 생겼습니다!

큰돌님께서 3분쯤에 질투심을 4로 하면 조건 충족을 못하신다고 하셨는데 보석을 못받는 학생이 생겨도 되므로 질투심 4일때는 조건은 만족하지만 최소값은 아니여서 정답이 아닌걸로 생각했습니다. 아래 그림을 봐주시면 질투심이 2일 때 학생수가 6명이 필요하므로 check함수의 n(학생수)>=num(질투심)을 충족하지 못한다고 생각했습니다. 제가 잘못 생각한 것일까요..?

c++코딩-테스트

답변 2

박찬울

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

큰돌

지식공유자

안녕하세요 효민님 ㅎㅎ

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

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

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

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

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; 
    }

이렇게 되는 것이죠.

감사합니다.

인프런 커뮤니티 질문&답변

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