결정 알고리즘

이분 탐색을 이용한 결정 알고리즘

1. 가능한 범위를 찾는다.

2. 이분 탐색을 이용해, 범위를 좁히는 함수를 만든다.

3. 해당하는 범위의 중간값이 조건을 만족하는지 확인하는 함수를 만든다.

 

#해당 길이만큼 곡의 길이가 되는지 확인하는 함수

	public int count(int[] arr, int capacity) {
		int cnt = 1, sum = 0;
		for (int x : arr) {
			if (sum + x > capacity) {
				cnt++;
				sum = x;
			} else
				sum += x;
		}
		return cnt;

	}

 

# 해당 거리만큼 말의 거리가 되는지 확인하는 함수

	public int count(int mid, int m, int[] arr) {
		int cnt=1;
		int ep=arr[0];
		
		for(int i=1;i<arr.length;i++) {
			if(arr[i]-ep>=mid) {
				cnt++;
				ep=arr[i];
			}
		}

		
		return cnt;
	}

 

 

: 먼저 한 개를 대입 후, 그 값을 이용해 구현한다.