공부 기록

1~n 까지 합 n(n+1)/2 <= S 의 방정식을 풀면 된다.

이 방정식을 풀면 n^2+n-2S<=0 이고, 방정식의 해를 구하면 n이 (-1+√ (1+8s))/2 와 (-1-√ (1+8s))/2 사이에 있으면 되고, 그 중에 큰 값이므로 (-1+√ (1+8s))/2을 버림하여 구하면 된다. 풀이는 아래와 같다.

import java.util.*;

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

		long s = in.nextLong();
		long n = (long) ((-1 + Math.sqrt(1 + 8 * s)) / 2);

		System.out.println(n);

	}
}

근데 문제 조건에 이분탐색으로 풀라는 이야기가 있었기 때문에.. 이분탐색으로 풀어보자면

n(n+1)/2를 s와 비교하여 아래와 같이 이분탐색으로 풀 수도 있다.

import java.util.*;

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

		long s = in.nextLong();
		long end = s;
		long start = 0;
		long answer = 0;

		while (start <= end) {
			long mid = (start + end) / 2;
			long sum = sum(mid);

			if (sum <= s) {
				answer = Math.max(answer, mid);
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}

		System.out.println(answer);
	}

	private static long sum(long n) {
		return n * (n + 1) / 2;
	}
}