알고리즘 스터디

Google Kick Start Round B 2번째 문제 Bus Routes입니다

 

총 N개의 버스가 있고 1번부터 N번버스까지 순서대로 타야합니다.

i번째 버스는 Xi의 배수인 날짜마다 운행합니다. 하루에 탈수있는 버스는 무제한입니다.

D일 까지 여정을 마쳐야 하고 가능한 늦게 출발하려고 할때 언제 출발하면 되는가 하는 문제입니다.

 

Limits

Time limit: 10 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Xi ≤ D.
1 ≤ N ≤ 1000.
It is guaranteed that it is possible for Bucket to finish her journey by day D.

 

Test set 1

1 ≤ D ≤ 100.

Test set 2

1 ≤ D ≤ 10^12.

 

C++을 사용한 제 풀이입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;

int n = 0;
long long d = 0;

void solve() {
	cin >> n >> d;
	vector<long long> a(n, 0);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	for (int i = n - 1; i >= 0; --i) {
		if (d % a[i] != 0)	d -= d % a[i];
	}

	cout << d << "\n";
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	for (int i = 1; i <= t; ++i) {
		cout << "Case #" << i << ": ";
		solve();
	}
}

간단하게 뒤에서부터 나머지 구해서 빼면 될것같아서 그대로 시도했는데 테스트셋 1번은 잘 맞고 2번이 안맞아서 왜지? 하고 문제를 봤는데 D랑 Xi가 10^12까지였네요..

다시한번 경계값을 잘 봅시다!

10~20분정도 걸렸는데 문제 해석하는데만 한참 걸렸네요 ㅠㅠ 영어 ㅠㅠㅠ