BOJ 25920 - Yonsei Formula 1

BOJ 25920 - Yonsei Formula 1

지문 해석에 어려움을 겪었다.

$dp[i][j]=i$ 번째 타이어를 쓸 것이고 $j$ 번 트랙을 돌았을 때 끝까지 가는데 필요한 시간이라고 하자.

$O(NM^2)$ DP 로 풀어줄 수 있다.

수학적으로 전처리가 필요한데, 어떤 타이어 $j$ 에 대해 트랙 $c$번을 도는 $Lc$ 이상의 거리를 가기 위한 최소 거리를 미리 계산해두어야 하고, 이건 이분탐색을 이용하면 $O(NM \log L)$ 에 처리할 수 있다.

단위 시간 $T$에 대해 몇 바퀴를 돌 수 있는지를 찾는다고 해보자.

$a_i, a_i-d_i, a_i-2d_i, \dots, a_i-(\dfrac{a_i-b_i}{d_i})d_i, \dots$ 처럼 계속 거리를 갈 수 있다.

그럼 일단 $a_iT$ 를 곱해준다음에 $d_i$ 의 합을 빼는것이다.

$\dfrac{a_i-b_i}{d_i}+1$ 까지는 $1$ 씩 증가하므로 시그마 공식을 쓰고, $b_i$ 가 될 때는 얼마나 더 시간초가 걸리는지를 이용해 $b_i$ 를 곱해준다.

말은 간단한데 구현이 조금 까다롭다.

오버플로우도 주의해야한다.

// i 번째 타이어를 쓰고 있고
// 트랙을 j 바퀴 돌았으며
// 끝까지 완주하기 위해 필요한 시간
int n, m, l, dp[1001][101], cycle[1001][101];
const int inf = 2e22;
vector<array<int, 3>> a;

int get_dist(int i, int mid) {
   int dec_t = (a[i][0] - a[i][1]) / a[i][2];
   int d = a[i][0] * mid;
   int t = min(mid - 1, dec_t - 1);
   int add_t = max<int>(0, mid - dec_t);
   d -= a[i][2] * ((t * (t + 1) / 2));
   d -= a[i][2] * dec_t * add_t;
   return d;
}

void pre_calc() {
   for (int i = 0; i < n; i++) {
      // 걸리는 분 수
      for (int track = 1; track <= 100; track++) {
         // dist를 가기 위해 얼마나 걸리는가?
         int dist = l * track;

         int l = 1, r = inf;
         while (l <= r) {
            // mid 분으로 갈 수 있는가?
            int mid = (l + r) / 2;

            if (get_dist(i, mid) >= dist) cycle[i][track] = mid, r = mid - 1;
            else l = mid + 1;
         }
      }
   }
}

int fn(int i, int j) {
   if (i == n && j < m) return inf;
   if (j == m) return 0;
   int &ret = dp[i][j];
   if (~ret) return ret;
   ret = inf;

   if (i != n - 1)
      mina(ret, fn(i + 1, j));
   // 다음 트랙 바퀴 수
   for (int nxt_j = j + 1; nxt_j <= m; nxt_j++) {
      mina(ret, cycle[i][nxt_j - j] + fn(i + 1, nxt_j));
   }

   return ret;
}

void solve() {
   memset(dp, -1, sizeof dp);
   cin >> n >> m >> l;
   a.resize(n);
   for (auto &[a, b, d]: a) cin >> a >> b >> d;
   //cout << get_dist(0, 1) << endl;
   //cout << get_dist(0, 2) << endl;
   //cout << get_dist(0, 3) << endl;
   pre_calc();
   cout << fn(0, 0);
}