문제 바로가기

https://www.acmicpc.net/problem/6236

문제 소개 및 재정의

N일 동안 M번 인출할수 있다.
1번 인출할때 K원씩 인출한다.
K원을 인출하고 N일 동안 매일 돈을 쓴다.
써야하는 돈은 매일 다르다.
어제 쓰고 남은 잔고가 오늘 쓸 돈 보다 많으면 인출안하고 쓸수있다.
만약 잔고가 오늘 쓸 돈보다 모자르면 남은 돈을 다시 입금하고 K원만큼 출금한다.
정확히 M번을 맞춰야한다. 그냥 마지막날에 출금회수가 M번보다 작으면 무지성으로 입금과 출금을 반복하면 된다.
왜냐면 입출금을 하는데 쿨다운타임이 없기 때문이다.
따라서 큰 의미가 없는 조건으로 보인다.
그리고 현우가 사용할수 있는 전체 돈에도 제약이 없다.

문제 패턴

어떤 조건을 만족하는 최적값 K를 구하는 문제이다.
최적값이 될수 있는 범위 안에서 이진탐색을 하며 이진탐색으로 값을 얻을때마다
해당 값이 조건을 만족하는지 확인하여 탐색방향을 결정하는 방식으로 풀수있다.

어떻게 풀까? - 이진탐색

포인트

k의 범위 정하기
최소값과 최대값을 구해야한다
최소값
i일날 써야하는 돈을 Ni라고 하자.
Ni의 최대값이 탐색범위의 최소값이 되어야 한다.
3일째 써야하는 돈이 500원이라고 하자.
그날 최소 500원 이상의 돈이 있어야 하는데 꺼낼수 있는 돈이 500원보다 적다면
3일을 통과할수 없게 된다.
정확히 말하면 출금을하고 통과할수있는지 확인하는 로직을 반복해서 출금회수가 M을 넘어설때 중단하고 탐색방향을 결정해도 된다.
하지만 이것보다는 탐색범위의 최소값을 Ni의 최대값으로 사용하는게 안전해보인다.
최대값:
M이 1일때를 가정하자. 한번의 출금으로 N일을 버텨야 한다.
그렇다면 최소한 매일 사용하는 돈의 합을 출금해야한다.
이 값 이상의 값은 범위로서 의미가 없다.

탐색방향 결정로직
K원을 M번 꺼내서 N일동안 돈을 낼수 있는지 파악해야 한다.
N일동안 생활하는데, 출금회수가 M번 이하라면 할수있는것이다.
따라서 탐색방향을 K를 줄이는 방향으로 범위를 줄인다.
N일동안 생활하는데, 출금회수가 M번 초과라면 할수없는것이다.
따라서 탐색방향을 K를 키우는 방향으로 범위를 늘린다.

코드

package study.week16;
import java.io.*;
import java.util.*;
public class BOJ_6236_용돈관리 {
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	// 세팅
	static int N;
	static int M;
	static int[] origin;
	static int total;
	static int bestK=Integer.MAX_VALUE;
	static int hardDay;
	// 메소드
	static void bs(int s, int e) {
		// 바닥 조건
		if(s>e) {
			// 추가작업?
			return;
		}
		// 재귀 파트
		int mid = (s+e)/2;
		if(check(mid)) {
			bs(s,mid-1);
		} else {
			bs(mid+1,e);
		}
	}
	static boolean check(int mid) { // mid=k
		int m = 0; 
		m++;// 최초 한번은 출금해야죠.
		int balance = mid;
		for (int i = 0; i < origin.length; i++) {
			if(m>M) { // 이미 실패했으니까 그만 돌자.
				break;
			}
			int Ni = origin[i];
			if(balance-Ni>=0) {
				balance -= Ni;
			} else {
				m++; // 돈 모자르네 출금해
				balance = mid; // 남은돈 입금후 K원만큼 출금했으니, 잔고는 K원
				balance -= Ni; // i번째 필요한 돈은 그대로 사용.
			}
		}
		if(m>M) {
			return false;
		} else {
			bestK = Math.min(bestK, mid);
			return true;
		}
	}
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		origin = new int[N];
		// 세팅
		for (int i = 0; i < N; i++) {
			int Ni = Integer.parseInt(input.readLine());
			origin[i] = Ni;
			total+=Ni;
			hardDay = Math.max(hardDay, Ni);
		}
		// 작업
		bs(hardDay,total);
		// 출력
		System.out.println(bestK);
	}// 메인

}

퍼포먼스

[ 20,604 KB | 204 ms ]

마무리

이진탐색 문제를 연습하기 아주 좋은 문제같다.