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

안녕하세요 큰돌님.

풀이를 몇번을 봤는데도 이해가 가지 않아서 질문드립니다.

1. 이분탐색으로 찾으려는 것

   
   - 실제 필요한 시간보다 조금 더 큰 시간
   - 즉, ret이 놀이기구를 타는데 걸린 총 시간이 됨

2. ret - 1 / a[i]

    

    

   
   

   - ex) 문제 예시 들어주신 것처럼 4분이 딱 되었을 때 새롭게 타는 사람 수를 빼주기 위해 하는 로직

3. 전체 묶음을 다 처리하고 놀이기구에 아무도 안 탄 상태로 가정하고 그 부분부터 한명씩 태우는 로직

이렇게 파악하긴 했는데, 아무리 봐도 2번, 3번이 전혀 이해가 가지 않습니다... 놀이기구 수만큼을 바로 태울 필요가 있나요? 처음 시작을 temp = m으로 시작하지 않고 temp = 0을로 시작하면 4분일 때 딱 7명 태운걸로 나와서 ret - 1 / a[i] 로직을 안해도 되지 않나요? 그리고 마지막에 총 걸린시간(ret) % a[i] 로직이 어떤 의미인건지 이해가 안 됩니다 ㅠㅠ 아래는 제가 선생님 코드를 이해하려고 주석을 달아본 코드입니다.

#include<bits/stdc++.h>
using namespace std;
#define max_n 60000000004
#define MAX_M 10004
typedef long long ll;
// ret : 총시간, temp가 m : 여기서 부터 시작
ll n, m, a[MAX_M], lo, hi = max_n, ret, mid, temp;
bool check(ll mid) {
  temp = m; // 놀이기구 수만큼은 바로 태울 수 있으므로 m명은 태우고 시작
  for (int i = 0; i < m; i++) 
    temp += mid / a[i];
  return temp >= n; // 총 걸리는 시간이 mid일 때 n명이상 태울 수 있는지
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) cin >> a[i];
  if (n <= m) { cout << n; return 0; }
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (check(mid)) {
      ret = mid; // 총 걸린 시간
      hi = mid - 1;
    } else
      lo = mid + 1;
  }

  // temp : 4분까지 태운 학생 수 -> 4분이 딱 됐을 때 바로 추가로 태울 수 있는데 그걸 뺀 순수하게 4분까지 태운 학생 수
  temp = m;
  for (int i = 0; i < m; i++)
    temp += ((ret - 1) / a[i]);
  
  // 4분부터 시작해서 다시 순차적으로 놀이기구 태움 -> 즉, 여기서는 놀이기구에 아무도 타있지 않은 초기 상태임
  for (int i = 0; i < m; i++) {
    if (ret % a[i] == 0) temp++; // % 연산의 결과가 0이 아날 경우 == 놀이기구에 이미 학생이 탑승되어 있음
    if (temp == n) {
      cout << i + 1 << "\n";
      return 0;
    }
  }
  return 0;
}