16401 과자 나눠주기

 

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

16401번: 과자 나눠주기

<최종 코드>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	
	
	static int N;
	static int M;
	static int snack[];
	static int length;
	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());
		
	
		snack = new int [M];
		StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
		
		for(int i=0; i<M;i++) {
			snack[i]= Integer.parseInt(st1.nextToken());
		}
	
		Arrays.sort(snack);
		search(1,snack[M-1]);
		System.out.println(length);
	}
		
		public static void search(int left, int right) {
			
		if(left>right) {
			return;
		}
		
		int mid=(left+right)/2;
    		int count=0;
		for(int i=0;i<M;i++) {
			if(snack[i]>=mid) {
				int n = snack[i]/mid;
			count+=n;
			}
		}
		
		if(count>=N) {
			if(length<mid) length = mid;				
			left = mid+1;
			search(left, right);
		}else if (count<N) {
			right= mid-1;
			search(left, right);
		}
	  }
    }

이분 탐색을 많이 풀어보지 못해서 참고자료 블로그를 참고했다.

 

 

#1. search 메소드 맨 아래 부분

 

1) count>=N

2) count<N 

인 두가지 경우가 생긴다.

 

1) count>=N 인 경우

length= mid 로 length 값을 바꿔주는데,

count>=N 이라, 조카 1명에게 줄 수 있는 막대 과자 최대 길이를 찾을 수 있기 때문에, length 값을 mid 로 바꿔서 출력하도록 하는 거고,

 

2) count<N 인 경우

조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 찾을 수 없기 때문에,

그냥 length=0 인 초기화 상태가 유지되도록 mid 값으로 바꿔주지 않는 것이다. 

 

 

 

# 2. static 변수

원래는 static 변수를 사용하면, 오류 발생 가능성이 크다고 배워서 사용하지 않으려고 했다.

그러면 search 메소드에 매개변수가 많아진다.

 

search(int N, int M, int left, int right, int snack[], int length)

그런데, 이런식으로 매개변수가 너무 많아도 코드가 좋지 않다고 한다.

그래서 어느 걸 선택해야 좋을지 모르겠다.

 

 

 

 

참고 자료 :

 

https://daily-life-of-bsh.tistory.com/189

[백준] 16401. 과자 나눠주기

 

 

----------------------------------------------------------------------(이 부분부터는 읽지 않으셔도 됩니다.)

원래 나는 N<=M, N>M 인 경우를 나눠서 처리하려고 했다.

예제에 나온 것을 보면 알 것이다.
첫번째 예제는 N(3)<=M(10) 이고
두번째 예제는 N>M이다.

 

일단 첫번째 예제를 보겠다.

3 10

1 2 3 4 5 6 7 8 9 10

 

N=3, M= 10 인 경우,

현재 존재하는 과자 수(10) > 필요한 과자 수 (3) 

이므로

기존에 주어진 과자 길이(1~10) 중 결과 값을 찾을 수 있다.

즉, 1~10 중 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구할 수 있다.

예제 출력값이 8인 것만 봐도 알 수 있을 것이다.

그래서 이 경우는

left = snack[0]=1,

right = snack[M-1]=10 

이렇게 범위를 정해준다.

 

 

그리고 두 번째 예제를 보겠다.

4 3

10 10 15

 

N=4, M = 3인 경우

현재 존재하는 과자 수(3)< 필요한 과자 수 (4) 

이다. 따라서 기존 존재하는 과자에서 길이를 잘라서 찾아야만 한다.

그래서 여러가지 경우가 존재하는데, 

10 10 15 중 제일 작은 값인 10을 기준으로

 

1. 10보다 같거나 작을 경우

1) 예제 입력이 10 10 15 이고 찾고자 하는 과자 개수가 4라면 정답은 7

2) 예제 입력이 10 10 20 이고 찾고자 하는 과자 개수가 4라면 정답은 10 

 

2. 10 보다 클 경우 

1) 예제 입력이 10 10 100 이고 찾고자 하는 과자 개수가 4라면 25

에서 답이 나올 수 있다.

 

때문에 이 경우는 10 10 15 의 범위 내에서 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구할 수 있는 게 아니라,

1~15(제일 길은 과자 길이) 에서 정답을 찾을 수 있다.

그래서

left= 1

right = snack[M-1] =15

이렇게 범위를 정해줄 수 있다.

 

즉 첫번째 예제는 

left = snack[0]

right = snack[M-1]

 

두번째 예제는 

left= 1

right = snack[M-1]

 

즉 left의 초기값이 달라질 수 있다.

 

 

그런 조건을 추가했을때, 아래 코드 부분이다

******* 친 부분

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	
	
	static int N;
	static int M;
	static int snack[];
	static int length;
	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());
		
	
		snack = new int [M];
		StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
		
		for(int i=0; i<M;i++) {
			snack[i]= Integer.parseInt(st1.nextToken());
		}
	
		Arrays.sort(snack);
		
		//*********************
		int left=0;
		int right=0;

		if(N<=M) { 
			left = snack[0]; 
			right=snack[M-1];
			
		}else if (N>M) { 
			left = 1;
			right=snack[M-1]; 
			
		}
		search(left,right);
		
		//**********************
		
		
		
		
		System.out.println(length);
	}
		
		public static void search(int left, int right) {
			
		if(left>right) {
			return;
		}
		
		int mid=(left+right)/2;
    	int count=0;
		for(int i=0;i<M;i++) {
			if(snack[i]>=mid) {
				int n = snack[i]/mid;
			count+=n;
			}
		}
		
		if(count>=N) {
			if(length<mid) length = mid;				
			left = mid+1;
			search(left, right);
		}else if (count<N) {
			right= mid-1;
			search(left, right);
		}
		}
		}

 

 

이 코드를 추가했을 때 결과가 윗 부분인데, 시간이(1288로 1316보다) 엄청 빠르지도 않다.

컴퓨터 속도가 빠른데, 내가 굳이 이런 경우까지 나눠서 할 필요가 없었다.

 

그래서 지움.

나중에 실력이 오른다면 너무 당연한 얘기겠지만, 이런 것도 기록해두면 나중에 읽어봤을 때 많이 성장했다는 걸 알 것 같아서 기록했다.