99클럽 코테 스터디 2일차 TIL (11561번: 징검다리)

문제

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

---

학습 키워드

• 이진 탐색

 

시도

• (시간초과) 1부터 차례대로 더하면서 n이 됐을 때, 더한 횟수 구하기
  • 완전 탐색?
  • 이렇게 구하게 되면 입력값으로 최대 10^16이 들어온다고 할 때, 10^8정도 소요된다. 모든 테스트케이스가 다 성공하는데 시간제한이 1초이므로 최악의 경우 한 개의 테스트만 돌면 끝나기때문에 시간초과가 발생한다.
• (성공) 등차수열 공식과 이진 탐색을 사용해서 값 구하기
  • 이진 탐색을 통해 (n * (n + 1)) / 2가 주어진 징검다리의 마지막 칸 보다 작거나 같은 경우, 밟았다고 판단하고 값을 저장해나가면서 가장 큰 값을 구하면 된다.

 

풀이

import java.util.*;

public class Main11561 {

	private static long answer = 1L;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			long n = sc.nextLong();
			answer = 1L;
			binarySearch(n, 0L, (long) Math.sqrt(2 * n));
			System.out.println(answer);
		}
	}

	private static void binarySearch(long n, long left, long right) {
		if (left > right) {
			return;
		}
		long middle = (left + right) / 2;
		if ((middle * (middle + 1)) / 2 > n) {
			binarySearch(n, 0L, middle - 1);
		} else {
			answer = Math.max(answer, middle);
			binarySearch(n, middle + 1, right);
		}
	}
}