[백준 17451] 평행 우주

www.acmicpc.net/problem/17451

17451번: 평행 우주

카테고리가 이분탐색이긴 한데 잘 모르겠다..

풀이 방법은 뒤에서 부터 순회하며 값을 찾는다.

 

현재의 값의 배수면서 && 이전 값보다 큰 최솟값을 찾는다.

 

#include <stdio.h>

using namespace std;
int n;
int arr[300001];
int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }

  long long res = arr[n - 1];
  for (int i = n - 2; i > -1; i--)
  {
    if (res % arr[i] == 0)
      continue;
    long long m = res / arr[i] + 1;
    res = arr[i] * m;
  }

  printf("%lld\n", res);

  return 0;
}