[Java] 백준 6236번: 용돈 관리

[문제 바로 가기] - 용돈 관리

💡 접근 방식

유형 : 매개 변수 탐색

left와 right의 초기 값 설정이 중요한 문제다.

처음에 아무 생각 없이(?) left를 money에서의 최솟값, right를 money에서의 최댓값으로 지정했다가 다음 반례에서 틀렸다. (반례의 답은 100)

5 5
1
1
1
1
100

★ 탐색 시 최솟값인 left가 money의 최댓값과 같거나 커야 인출했을 때 사용해야 하는 돈만큼 사용할 수 있다. 그리고 최댓값인 right가 money의 모든 금액의 합과 같거나 작아야 한다.
(right는 금액의 최댓값인 10000과 일수인 N의 곱으로 설정해주어도 된다.)

인출 판단 로직

	int count = 1;
	int wallet = 0;
			
	for (int i = 0; i < N; i++) {
		wallet += money[i];
				
		if (wallet > mid) {
			count++;
			wallet = money[i];
		}
	}

count가 M보다 작거나 같을 경우

• 인출 금액을 낮춰야 하므로 right = mid - 1

count가 M보다 클 경우

• 인출 금액을 높여야 하므로 left = mid + 1

반복문이 끝나고 가장 작은 인출 금액을 찾아야 하므로 left를 출력해주면 된다.

+) 2025.02.11 추가한 내용

🐝 이분 탐색 / 매개 변수 탐색 시 꿀팁

평소 나는 mid 값을 구할 때 다음과 같이 작성한다.

int mid = (left + right) / 2;

하지만 left와 right의 합이 int의 범위를 넘어서는 경우, 오류가 발생할 수 있기 때문에 스터디원분께서 추천해준 방식이 있다!

int mid = left + (right - left) / 2;

이 코드는 혹여나 그런 상황에서도 오류가 발생하지 않으므로 기억하기!

---

풀이

import java.util.*;
import java.io.*;

/**
 * 백준 6236번 용돈 관리
 * - 매개 변수 탐색
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int money[] = new int[N];
		int left = 0;
		int right = 0;
		
		for (int i = 0; i < N; i++) {
			money[i] = Integer.parseInt(br.readLine());
			left = Math.max(left, money[i]);
			right += money[i];
		}
		
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int count = 1;
			int wallet = 0;
			
			for (int i = 0; i < N; i++) {
				wallet += money[i];
				
				if (wallet > mid) {
					count++;
					wallet = money[i];
				}
			}
            
			if (count <= M) {
				right = mid - 1;
			} else if (count > M) {
				left = mid + 1;
			}
		}
		
		System.out.println(left);
	}
}