문제 URL : https://www.acmicpc.net/problem/16401
16401번: 과자 나눠주기
첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN
www.acmicpc.net
문제 접근법 : 과자를 잘랐을때 n명에게 똑같이 나눠줄수 있을때 그길이를 최대로 만들라는 문제입니다.
이분탐색으로 과자를 잘라보고 n명이상으로 나눠줄수있는지 확인하면 자르는 길이를 더 늘려보고
작다면 자르는 길이를 낮추면서 이분탐색을 진행하면 쉽게 풀수있는 문제입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
//By
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;
vector<ll> v;
ll Max = 0;
void input() {
cin >> m >> n;
v.resize(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
Max = max(Max, v[i]);
}
}
void solve() {
int first = 1;
int last = Max;
int res = 0;
while (first <= last) {
int cnt = 0;
int mid = (first + last) / 2;
for (int i = 0; i < n; i++) {
cnt += v[i] / mid;
}
if (cnt>=m) {
res = max(res, mid);
first = mid + 1;
}
else {
last = mid - 1;
}
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 2666 벽장문의 이동 (0) | 2021.10.05 |
|---|---|
| 백준 10835 카드게임 (0) | 2021.10.05 |
| 백준 11066 파일 합치기 (0) | 2021.09.29 |
| 백준 6324 URLs (0) | 2021.09.01 |
| 백준 1938 통나무 옮기기 (0) | 2021.08.31 |
