개요

백준 62336번: 용돈 관리

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

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

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

접근 방식

1. 사실 문제를 이해를 못해서 처음 받아들인 생각은
   한글말을 보고 이해한 건 무조건
   돈을 K원 인출-> 첫날에 K보다 작은 돈이면 ->지갑에 K-첫날돈 소유
   -> 둘째날에 K-첫날돈보다 작은돈이면-> 지갑에 k-첫날돈-둘째돈 소유
   -> 셋째날에 지갑에 있는 돈보다 사용할 돈이 더 많다면 새로 인출 이런식으로 이해해서
   무조건 사용할 돈이 소유 돈보다 많을때만 인출을 하여 총 횟수를 M을 맞추는 것이였다.

   그래서 M을 맞추는 데다가 초점을 두다보니 헷갈렸다.
   백준의 질문게시판의 반례 중
   5 4
   100
   100
   100
   100
   100의 답이 200이라는 것이였다.
   내가 위의 적은 논리라면 k가 200원이라면
   (100,100) / (100,100) / 100 이런식으로 세부분으로 나눠지는게 맞는데
   네 부분을 나누는 문제의 k원이 200이라고 하니 말이다.

2. 이해가 안가서 여기저기 찾아보니 이 문제는 [백준2343(기타 레슨)] 문제와 같은 문제다.

   M보다 적은 횟수를 인출한다해도 문제에 써있는

   다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.

   이 조건 때문에 M보다 적게 범위를 나눠도 답이 될 수 있다.

   위에 예시도 내가 위에 적은 무조건 횟수를 M으로 맞춰야하는 논리라면
   (100,100) / (100,100) / 100 이렇게 세 부분으로 나눠서 M인 4가 안 되지만

   저 조건 때문에 맨 앞 부분이나 중간부분의 (100,100) 을 쪼개서
   100 / 100 /(100, 100) / 100
   이렇게 M을 4로 맞출수가 있기 때문이다.

   결론은 문제를 잘 해석 안 했던것이다.

   그래서 M보다 적은 횟수를 인출하는 모든 답 중에서 최솟값을 구하기 위해
   이분탐색을 사용했디.
   

코드

#include<iostream>
using namespace std;

int N, M;
int inputArr[100'001];

// 입력값
void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> inputArr[i];
	}
}

//한글말을 보고 이해한 건 돈을 K원 인출-> 첫날에 K보다 작은 돈이면 ->지갑에 K-첫날돈-> 둘째날에 K-첫날돈보다 작은돈이면 k-첫날돈-둘째돈  -> 셋째날에 k-첫날돈-둘1재돈보다
//크다면 새로 인출 이런식으로 이해 했는데

//2343문제와 같이 M을 맞추기 위해서 남은돈을 우겨써도 된다는 뜻인듯 

/// <summary>
/// price값을 M번 인출가능한지 여부 반환 함수
/// </summary>
/// <param name="price"></param>
bool checkIsPriceAnswer(int price) {
	//M 번 인출가능한지 확인하는 변수, 임시 가격값
	int limit = M, tmpPrice = price;

	for (int i = 0; i < N; i++) {
		if (inputArr[i] > price) {
			if (price == 500) cout << "here";
			return false;
		}
		//현재 가격보다 해당 날짜에 사용액이 더크다면
		if (inputArr[i] > tmpPrice) {
			//한번 인출 후 
			limit--;
			//limit이 음수가 되면 false 반환
			if (limit <= 0) {
				if (price == 500) cout << "here";
				return false;
			}
			//tmpPrice새로 설정
			tmpPrice = price;
		}
		tmpPrice -= inputArr[i];
	}
	return true;

}

void solution() {
	int mid=0,low = 0, high = 1'000'000'000;
	while (low + 1 < high) {
		mid = (low + high) / 2;
		(checkIsPriceAnswer(mid) ? high : low) = mid;
	}
	cout << high;


}

int main() {
	input();
	solution();
}

생각

답이 입력값보단 큰 값이여야 한다는 생각에 low를 입력값중 제일 큰 값으로 잡아줬더니
while(low+1<high)에 걸려서 답+1값이 계속 나왔다.

어차피 low가 0이 들어가도 high값에 답이 되는 최소값, low에 불가능한 값이 들어갈텐데 말이다.