메모리
시간
1504 KB
20 ms
문제 풀이
일 수 만큼 주어지는 금액대로 매일매일 용돈을 사용해야 하고
그 금액에 맞게 출금 횟수를 맞추어서 출금할 최소 금액을 구하는 문제이다.
출금하고 사용한 금액이 다음 날 사용할 금액보다 크다면 더 출금하지 않고 남은 잔돈에서 사용을 한다.
만약 남은 금액이 다음날 사용할 금액보다 적다면 남은 금액은 재입금한 뒤 출금한다.
이분탐색 문제로 min, max 범위를 정한뒤 중간 값을 구해 주어진 조건에 맞게 좁혀가며 값을 구하는 문제이다.
1번의 출금으로 하루 용돈을 사용할 수 있어야 하니 최소값은 가장 용돈이 큰 날의 값으로 설정하고
max는 최소 1번의 출금이 있어야 하니 모든 용돈의 합으로 설정해주었다.
Code
#include <cstdio>
int arr[100000];
int count_m(int mid, int n)
{
int count = 0;
int change = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] > change)
{
count++;
change = mid;
}
change -= arr[i];
}
return count;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
int mid, min = 0;
int max = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
if (min == 0)
min = arr[i];
else if (min < arr[i])
min = arr[i];
max += arr[i];
}
while (min <= max)
{
mid = (min + max) / 2;
if (count_m(mid, n) > m)
min = mid + 1;
else
max = mid - 1;
}
printf("%d", min);
return 0;
}
C++
복사
