6-A_ 2792 보석상자 강의 질문
안녕하세요 큰돌님 강의를 듣다가 질문이 생겼습니다!
큰돌님께서 3분쯤에 질투심을 4로 하면 조건 충족을 못하신다고 하셨는데 보석을 못받는 학생이 생겨도 되므로 질투심 4일때는 조건은 만족하지만 최소값은 아니여서 정답이 아닌걸로 생각했습니다. 아래 그림을 봐주시면 질투심이 2일 때 학생수가 6명이 필요하므로 check함수의 n(학생수)>=num(질투심)을 충족하지 못한다고 생각했습니다. 제가 잘못 생각한 것일까요..?
답변 2
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;
}이렇게 되는 것이죠.
감사합니다.
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
21
2
2주차 개념#12 트리 순회
0
20
2
백준사이트가 종료된다고 합니다.
0
240
2
백준 서비스 종료
9
769
1
sk 하이닉스 코테 대비
0
358
2
3-G 최댓값 질문
0
50
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
82
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
100
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
165
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
49
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
67
2
함수별 시간복잡도
0
72
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
52
2
1-I 문제 질문 드립니다.
0
76
2
2-P 질문입니다.
0
56
1
mac에서 시작하기 관련
0
88
2
5-Q 질문
0
63
2
풀이 코드 질문
0
64
2