Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <vector>
- using namespace std;
- long long n, k, maxx = 0, ans = 0;
- vector<int> v;
- long long count(int mid) {
- long long ccnt = 0;
- for (int i = 0; i < v.size(); i++) {
- ccnt += v[i] / mid;
- //if (v[i] / mid == 0) return -1;
- }
- return ccnt;
- }
- void go(long long start, long long end) {
- if (start > end) return;
- long long mid = start - (start - end) / 2;
- long long cnt = count(mid);
- //printf("start = %lld mid = %lld end = %lld cnt = %lld\n", start, mid, end, cnt);
- //답 구하기 부분
- if (cnt >= n && mid > ans) { // ★★★ cnt==n하면 안 되고 cnt>=n 해줘야 한다 ★
- ans = mid;
- }
- //재귀 부분
- if (cnt > n) {
- go(mid + 1, end);
- }
- else if (cnt < n) {
- go(start, mid - 1);
- }
- else { // cnt==n 일때도 계속 해줘야함
- go(mid + 1, end); // ★ go(mid,end)하게 되면 계속 같은 값으로 도는 현상 발생
- //go(mid+1,end);
- }
- }
- int main() {
- long long tmp;
- scanf("%lld %lld", &k, &n);
- for (int i = 0; i < k; i++) {
- scanf("%lld", &tmp);
- v.push_back(tmp);
- if (maxx < tmp) maxx = tmp;
- }
- go(1, maxx); // ★ go(0,maxx)하게 되면 0으로 나누는 값이 생겨서 런타임 에러 발생!
- printf("%lld\n", ans);
- return 0;
- }
Add Comment
Please, Sign In to add comment