99클럽 코테 스터디 2일차 TIL : 이분탐색(백준11561. 징검다리)

11561. 징검다리

 

 

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

 

---

 

 

⭐나의 풀이

1 ~ N개 징검다리

1. 첫 징검다리 아무거나 밟을 수 있음
2. 두번째 점프부터는 이전 점프한 거리보다 1이상 긴거리
3. N번 징검다리는 반드시 밟아야한다.
4. N번 징검다리 이후는 점프하지 않아 규칙적용X

1<=N<=10^16
승택이가 밟을 수 있는 최대 징검다리 수 출력하기

예1) 1
1

예2) 2
1

예3) 3
2

예4) N=100
13

 

수열 a
1 3 6 10 15 21 28 36 45 55 66 78 (91-점프x) 100(대신점프o) =>13개
= n(n+1)/2

=> 해당 수열 a 에서 N보다 작은 것 중 가장 큰 것의 index찾기(1부터 시작)

 

"1 + 2 + 3 + ... + k <= N을 만족하는 가장 큰 k" 찾기.

예) N=15일 경우

답: k=5. (즉, 1+2+3+4+5=15)

 

=> 이분탐색으로 해결

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int caseCnt = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<caseCnt;i++) {
			long num = Long.parseLong(br.readLine());
			long result = 0;
			
			if(num==1||num==2) {
				result=1;
			}else {
				result = getMaxCount(num);
			}
			
			//sb.append("num:"+num+", result: "+result+"\n");
			sb.append(result+"\n");
		}
		
		System.out.println(sb);

	}

	private static long getMaxCount(long n) {
		long left = 1;  // 시작값을 1로
	    long right = (long) Math.sqrt(2 * n);  // 적정 범위로 줄임
		long result = 0;
		
		while(left<=right) {
			long mid = (left+right)/2;
			long num = (long)mid*(mid+1)/2;
			
			if(num==n) {
				return mid;
			}else if(num<n){
				result = mid;
				left = mid+1;
			}else {
				right = mid-1;
			}
		}
		return result;
	}

}

 

 ⭐오늘의 회고

✔ 변수 타입

문제) n값의 제한이 1<=n<=10^16 이기 때문에, int로 변수를 설정 했더니 오버플로우가 일어나 정답을 정확히 반환하지 않았음

개선) long형으로 변경

참고) int와 long

• int 타입: 4바이트 크기이며, 표현 가능한 범위는 -2,147,483,648 ~ 2,147,483,647이다.
  (약 −2×10^9에서 +2×10^9까지)
• long 타입: 8바이트 크기이며, 표현 가능한 범위는 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807이다. (약 −9×10^18에서 +9×10^18까지)

=>  int 타입의 범위를 넘어서는 큰 숫자(예: 10^10이나 10^16 등)를 다룰 때는 long을 사용해야한다.

 

 

✔ 탐색 범위의 최소화

문제) long right 값을 n으로 지정했을 때, 연산이 제대로 이루어지지 않는지 오답으로 나옴

private static long getMaxCount(long n) {
		long left = 1;  // 시작값을 1로
	    long right = (long) Math.sqrt(2 * n);  // 적정 범위로 줄임 - n
		long result = 0;
		
		while(left<=right) {
			long mid = (left+right)/2;
			long num = (long)mid*(mid+1)/2;
			
			if(num==n) {
				return mid;
			}else if(num<n){
				result = mid;
				left = mid+1;
			}else {
				right = mid-1;
			}
		}
		return result;
	}

 

개선)

예를 들어 N=10^16라고 하면, k의 최대 값은 약 141,421이다.  따라서 해당 값 이하에서 탐색하면 충분하다.

하지만 나의 경우엔 범위를 지나치게 크게 설정 left = 1, right = n 으로 했었는데, 이의 경우를 생각해보면

• 이진 탐색에서 mid를 구할 때, 처음 mid 값은 (1+10^16)/2 ≈ 5×10^15 가 된다.
• 그 후, mid * (mid + 1) / 2를 계산하는 과정에서 10^30에 가까운 값이 나오며, 이 값은 long 타입의 최대값인 9.2×10^18을 훨씬 초과하게 된다. => 오버플로우가 발생

따라서 탐색 범위를 최소화( right <= sqrt(2n))해야한다.

 

참고)

* 문제: 합이 n을 넘지 않는 최대 k 찾기

 

주어진 등차수열의 합이 n을 넘지 않도록 하는 가장 큰 k를 찾는 것이 목표이다.

등차수열의 합은 다음과 같이 표현된다.

 

1 + 2 + 3 + ⋯ + k = k⋅(k+1) /2

​

이 합이 n을 넘지 않도록 하는 최대 k를 찾아야 하므로, 다음과 같은 부등식을 세울 수 있다.

k⋅(k+1) / 2  ≤ n

 

이 식을 k에 관한 식으로 풀어서 답을 구할 수 있다.

 

* 계산 과정

1. 양변에 2를 곱해 분수를 없앤다: k⋅(k+1) ≤ 2n
2. 이를 전개해서 정리하면: k^2+k ≤ 2n
3. k^2+k−2n ≤ 0 형태로 바꾼 다음, 근의 공식으로 k의 근을 구할 수 있다:
   

   

   
   ​​
4. 여기서 근의 공식에서 음수는 의미가 없으므로, 양수 해만 고려하면 된다.
   ​​

 

=> k의 값이  sqrt(2n​)에 비례한다.

​