용돈 관리

백준 문제

[Silver II] 용돈 관리 - 6236

문제 링크

성능 요약

메모리: 1508 KB, 시간: 20 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2023년 12월 25일 16:51:58

문제 설명

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

TIL

• 만일 int a, int b가 표현가능 범위 내의 최댓값을 가지고 있다면, mid=(a+b)/2;는 오버플로우의 가능성을 지니고 있다. 따라서 mid=b/2+(a-b)/2와 같이 구하면 안전하다.
  (이 문제에서는 필요 없긴 하다.)

FeedBack

• 전형적인 parametric search 문제이다.
  그러나 돈이 부족한 경우에 대한 것을 고려하지 않아 다른 사람의 코드를 참고하였다.
  예제 입력에서 주어진 경우가 아니여서 이를 생각하기가 까다로웠고 시간이 오래걸렸다.
  천천히 문제의 경우를 나누어 보도록 하자.

내 접근

첫 시도 : parametric search 쓰면 개 쉬운 문제
그런데 출금 단위가 애초에 부족한 경우를 깊게 고민하지 않아 시간을 많이 허비하였다.

내 코드

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 100000000

int main()
{
	//input
	int days, limit;
	long long low=MAX,high = 0;
	scanf("%d %d", &days, &limit);
	int* plans = (int*)malloc(sizeof(int) * days);
	for (size_t i = 0; i < days; i++) {
		scanf("%d", &plans[i]);
		low = low > plans[i] ? plans[i] : low;
	}
	
	
	for (size_t i = 0; i < days; i++) high += plans[i];

	
	//parametirc search
	while (low <= high) {
		int mid = (low + high) / 2;
		int count=0;//인출 횟수
		int cur=0; //현재 수중에 있는 돈
		bool pass = true;
		for (size_t i = 0; i < days; i++) {
			if (mid < plans[i]) {
				pass = false;
				break;
			}
			if (cur < plans[i]) {//돈이 부족하다면
				count++;
				cur = mid;

			}
			cur -= plans[i];
			
		}
		if (count > limit||!pass) low = mid + 1; //불가능 -> 더 큰 쪽에서 mid를 찾아
		else high = mid - 1;//가능 -> 더 작은 쪽에서 mid찾아
	}
	
	printf("%d", low);
	free(plans);

	return 0;
}