[백준] 6236 용돈 관리 - 파라매트릭 서치(Paramatric Search) JAVA

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

6236번: 용돈 관리

코드설명

파라매트릭 서치 문제입니다.

 

1. 문제에 대한 이해가 중요한 문제입니다.

아래 문제조건을 보면

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

위 문제를 보면, 남은 금액은 통장에 다시 집어넣는다는 조건을 이해하고 구현해야합니다. 

제가 처음에 구현한 코드는, 하루에 K원 인출을 한번만 가능한것이 아닌 여러번 가능하다고 생각했기에, K원이 답보다 더 작게 나옵니다.

하지만, 문제에서 주어진 바로는 한번 인출했을때 한번 인출한다면, 일주일에 사용하게 되는 금액보다는 크거나 같아야한다는 조건으로 해결해야합니다. 그렇지 않을경우, 비효율적으로 돈을 뽑고, 통장에 넣게 되므로 통장에서 돈을 안뽑아도될때 뽑게됩니다.

 

제가 처음에 이해한바로는, K원 인출을 한번만 가능한것이 아닌 여러번 가능하다고 생각했습니다.

if(leftmoney < 0) { //남은금액이 음수라면, 새로 돈을 가져온뒤, (현재 가지고있는 돈) - (사용할 금액) = (남은금액)
    cnt +=  ( arr[i] / middle ) + ( arr[i] % middle > 0 ? 1: 0 );
    money = middle * cnt;

    money -= arr[i];
    money = middle; 
}

 

 

2. start 값을 이용 금액의 최대값으로 설정합니다. 

for(int i=0;i<N;i++) {
    st = new StringTokenizer(br.readLine());
    arr[i] = Integer.parseInt(st.nextToken());
    start = Math.max(start, arr[i]);
}

• 위의 1번 문제와 연관된것으로 이렇게 start값을 설정함으로써 한번 인출하면 무조건 하루는 사용할 수 있습니다.

코드

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N, M;
	public static int[] arr;
	public static int start = 0, end = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    		start = Math.max(start, arr[i]);
    	}
    	
    	paramatricSearch();
    }
	
	public static void paramatricSearch() {
		start = start;
		end = 1000000000; // 최대 10000 * 100000 = 1000000000
		
		while(start <= end) {
			int middle = ( start + end ) / 2;
			
			int cnt = 1; //처음에는 돈 빌리고 시작함
			int nowMoney = middle;
			for(int i=0; i<N; i++) { 
				if(nowMoney - arr[i] < 0) { //돈이 부족하면, 돈을 다시 인출
					nowMoney = middle;
					cnt += 1;
				}
				
				nowMoney -= arr[i];  //돈을 사용
				
			}
			
			if(cnt > M) { //사용한 횟수가 M보다 크다면, 돈의 크기를 크게해줘야 cnt가 줄어듬 
				start = middle + 1;
			}else { //사용한 횟수가 M보다 작거나 같다면, 돈의 크기를 작게해줘야 cnt가 증가함
				end = middle - 1;
			}
			
		}
		System.out.println(start);
		
	}
	

}

 

잘못푼 코드, 통장에서 금액을 여러번 뽑을 수 있고, 인출값으로 하루의 최대사용량을 보장하지 않는 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N, M;
	public static int[] arr;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	paramatricSearch();
    }
	
	public static void paramatricSearch() {
		int start = 0; //시작은 0 원부터
		int end = 1000000000; // 최대 10000 * 100000 = 1000000000
		
		while(start <= end) {
			int middle = ( start + end ) / 2;
			
			int money = middle;
			int cnt = 0;
			
			for(int i=0; i<N; i++) {
				int leftmoney = money - arr[i]; // (현재 가지고있는 돈) - (사용할 금액) = (남은금액)
				
				if(leftmoney < 0) { //남은금액이 음수라면, 새로 돈을 가져온뒤, (현재 가지고있는 돈) - (사용할 금액) = (남은금액)
					cnt +=  ( arr[i] / middle ) + ( arr[i] % middle > 0 ? 1: 0 );
					money = middle * cnt;
					
					money -= arr[i];
                    money = middle; 
				}
				else if(leftmoney >= 0) { //남은 금액이 양수라면, (현재가지고있는 돈) = (남은금액)
					money = leftmoney;
				}
				
				System.out.println(" arr[i]:" + arr[i] + " money:"+money+ " leftmoney:"+leftmoney+" cnt:"+cnt);
			}
			System.out.println("money:"+middle+"  cnt:"+cnt);
			System.out.println("--------------------------------");
			if(cnt > M) { //사용한 횟수가 M보다 크다면, 돈의 크기를 크게해줘야 cnt가 줄어듬 
				start = middle + 1;
			}else { //사용한 횟수가 M보다 작거나 같다면, 돈의 크기를 작게해줘야 cnt가 증가함
				end = middle - 1;
			}
			
		}
		System.out.println(start);
		
	}
	

}

 

 

3%에서 틀린 코드입니다.

아래의 코드가 틀린 이유는, 탐색범위입니다. 

현재 저는 0원부터 10001원까지로 처리했었는데요, 우선 시작점인 0 원부터 살펴보겠습니다.

우선 0원이 아닌 현우가 통장에서 인출해야 할 최소 금액의 최대값 - 1 이어야 합니다. ( -1  인 이유는 최대값도 해당 범위에 포함시켜야 하기때문)

이유는, lo값은 탐색할 수 있는 최소 금액을 의미합니다. 이떄 이 최소금액이 최소한 하루의 지출을 감당할 수 있는 있어야 하므로  lo는 최소인출금액이 됩니다. 만약 lo가 0 이라면, 아무리 연산을 하더라도 ret 은 항상 <= M 보다 작으므로 무의미합니다. 

그렇다면, 이런 생각이 듭니다. 이진탐색의 시작범위가 작은것이 문제지 큰것이 왜 문제인가? 범위가 크다면 효율적이지 않을뿐 값을 찾아야하는 것 아닌가? 라는 생각입니다. 

그렇지만, 그렇지 않습니다... 저도 완전히 납득이 가지는 않아서, 완벽하게 설명은 불가합니다..

이유를 추축해보면, 저희의 함수의 전제조건은 'lo' : 최소 인출 금액의 하한선. 'hi' : 최대 인출금액의 상한선 입니다. 

이떄 lo에 최소 인출 금액의 하한선은 현수가 모든 날에 돈을 뽑을 수 있느냐는 조건입니다.

만약 lo가 0 이 들어간다면, 현수는 특정일에 절대로 돈을 못뽑는 경우가 생깁니다. 

이는, 결정함수에서 결국에 계속해서 TRUE 값을 반환하면서 right 범위가 계속해서 작아지는 결과를 반환할 것 입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(optimize(0, 10001));
	}
	
	static int optimize(int lo, int hi) {
		int left = lo;
		int right = hi;
		
		while(left + 1 < right) {
			int mid = (left + right) / 2;
			if(decision(mid) == true) {
				right = mid;
			}else {
				left = mid;
			}
		}
		return right;
	}
	
	static boolean decision(int moneyOut) {
		//처음에는 인출하고 시작합니다.
		int ret = 1;
		int curMoney = moneyOut;
		for(int i=0; i<N; i++) {
			if(curMoney - arr[i] >= 0) {
				curMoney -= arr[i];
			}
			else if(curMoney - arr[i] < 0) {
				curMoney = moneyOut - arr[i];
				ret += 1;
			}
		}
		return ret <= M;
	}
	
	
}

 

 

정답코드입니다.

우리가 실행하는 ParamaticSearch 함수가 현우가 통장에서 인출해야 할 "최소 금액"을 찾기 위한 것이다 라는것을 유의합니다. 그렇기에 범위에는 현우가 인출할 수 있는 하한선의 값, 현우가 인출할 상한선의 범위로 설정해서 값을 찾아나갑니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		int max = 0;
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
			max =Math.max(max, arr[i]);
		}
		
		System.out.println(optimize(max - 1, 1000000001));
	}
	
	static int optimize(int lo, int hi) {
		int left = lo;
		int right = hi;
		
		while(left + 1 < right) {
			int mid = (left + right) / 2;
			if(decision(mid) == true) {
				right = mid;
			}else {
				left = mid;
			}
		}
		return right;
	}
	
	static boolean decision(int moneyOut) {
		//처음에는 인출하고 시작합니다.
		int ret = 1;
		int curMoney = moneyOut;
		for(int i=0; i<N; i++) {
			if(curMoney - arr[i] >= 0) {
				curMoney -= arr[i];
			}
			else if(curMoney - arr[i] < 0) {
				curMoney = moneyOut - arr[i];
				ret += 1;
			}
		}
		return ret <= M;
	}
	
	
}