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

안녕하세요 sol님 ㅎㅎ

항상 sol님께 답변하다보면 야스오가 생각이 납니다.

소리에게돈~

https://youtu.be/ezFdNAP94T4

우선 놀이공원을 타는 아이들을 태울 수 있는 시간을 한 묶음단위로

정확한 시간보다 더많은 시간을 구하는것으로 이해했습니다.

>> 네 맞습니다. 더 많은 시간이긴 하나 약간의 그 끝지점보다 조금 많은 시간을 구하는 것입니다.

그래서 check 함수에서 아래와 같이 정확한 시간을 체크하지 않는 건가요?
정확한 시간을 구하면 마지막 학생이 어떤 놀이기구를 타는것을 구하는것이 어렵기 떄문일까요?

>>

check함수로 정확한 시간을 구하는게 아니라 이분탐색을 통해서 적절한 덩어리를 찾아내는게 저 check함수의 역할입니다. 애초에 정확한 시간을 찾아내려면 선형탐색으로 ~~가 돼? 안돼? 하면서 찾아내는 방법이 있겠죠. 하지만 그렇게 되면 너무나도 시간복잡도가 크기 때문에 그렇게 하면 안되고, 이분탐색으로 "일단은" 이 덩어리로 커버 가능한거야? 를 묻는게 check함수의 역할입니다.

예를 들어 놀이기구는 3개, 4분, 2분, 1분짜리가 있다고 했을 때 4분안에 총 10명을 태울 수 있겠죠?

그 10명을 기반으로 n이 만약에 9, 8, 7 ... 일 때 그것보다 커? 를 체크하는 함수인 것이죠.

어떠한 "시간"을 기반으로 카운팅을 해서 아니 몇명 태울 수 있는데를 체크해서 원래의 값보다 조금은 많은 시간을 만들어 냅니다.

(그리고 제 check함수는 다음과 같습니다.)

bool check(ll mid){
    temp = m; 
    for(ll i = 0; i < m; i++)temp += mid / a[i];
    return temp >= n;  
}

그래서 정확한 시간을 구하기 위해 ret - 1을 하며 시간을 이전 묶음단위로 재정의 하고나서

temp++을 하는 조건문을 이해지 못하겠습니다.

ret은 정확한 시간이 아닌 원래 구하는 시간보다 +되어있는 시간인데
왜 거기에 놀기기구의 시간을 % 연산을 해서 temp를 ++할까요?

>>

그렇기 때문에 ret - 1을 하는 겁니다. ret은 이미 + 되는 시간(필요로 하는 시간보다 조금은 더 큰 시간)이기 때문이고 거기서 -를 해서 >> 그 다음부터 ++를 해서 차근차근 아이를 놀이기구에 탑승시키는 것이죠.

자, 앞의 있는 그림으로 설명해볼게요.

n = 8라고 해볼게요. (아이의 수)

시간 4분짜리가 10명을 태울 수 있네요? check 함수에 걸려서 우리는 4분이라는 시간을 얻어냅니다.

자 여기서!! 4분 - 1분을 합니다.

3분이되죠?

자, 그러면

    temp = m;
    for(ll i = 0; i < m; i++) temp += ((ret - 1) / a[i]); 
    

앞의 코드를 통해서

3 + 0 + 1 + 3 을 해서 7이 나오네요?

자자, 이제부터 다시 처음부터 놀이기구를 태우게 됩니다.

이 때 놀이기구에 이미 탑승되어있는건 제외해야 하니,

    for(ll i = 0; i < m; i++){
        if(ret % a[i] == 0)temp++; 
        if(temp == n){
            cout << i + 1 << '\n';
            return 0; 
        }
    } 

모듈러 연산으로 해당부분을 처리합니다.

또한 기존 ret을 중심으로 해놓습니다. 7분짜리는 해놓았고 이제 시간은 8분이 되었기 때문이죠.

이 때 맨 앞에 있는 4 짜리 1번을 탑승하게 되는 것입니다.

즉, 마지막 아이가 탑승할 놀이기구의 번호는 1이 되는 것입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.