코드 포스(Code Force) 915 - A. Garden

문제 유형: 수학

문제 URL: https://codeforces.com/contest/915/problem/A

  정원은 길이가 K인 선분(Segment) 형태로 표현됩니다. 또한 N개의 그릇에 물을 담아서 농작물에 물을 주려고 합니다. i번째 그릇은 한 시간에 Ai 길이의 연속적인 공간에 물을 줄 수 있도록 해줍니다. 이 때 한 번 물을 준 곳은 더 이상 주지 않으며 주인공은 하나의 그릇을 선택하여 가능한 빠르게 농사를 짓는 전체 공간에 물을 주고자 합니다. 이 때 주인공이 가장 적은 시간으로 정원에 물을 줄 때의 시간을 구하면 됩니다.

  이 문제는 길이가 K인 전체 정원에 물을 주어야 하며 남는 공간이 없어야 하고, 한 번 물을 준 곳은 더 이상 줄 수 없다는 점에서 단순히 약수를 판별하는 문제입니다. 주어진 그릇의 크기 중에서 K의 약수로 가장 큰 것을 고르면 됩니다. 따라서 K를 해당 약수로 나눈 값을 출력하도록 하면 정답 처리를 받을 수 있습니다. 또한 항상 하나 이상의 그릇은 정원의 모든 공간에 물을 줄 수 있도록 입력이 주어진다고 합니다.

※ 예시 입출력 ※

input

Copy

3 6
2 3 5

output

Copy

2

input

Copy

6 7
1 2 3 4 5 6

output

Copy

7

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#include <limits.h>

using namespace std;

int main(void) {
	int n, k;
	cin >> n >> k;
	int res = INT_MIN;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if(k % x == 0) {
			res = max(res, x);
		}
	}
	cout << k / res;
	return 0;
}