문제

당신은 프로포즈를 위해 촛불을 삼각형으로 배치하고 있다. 촛불을 K단 크기로 배치하면, 1단에는 K개의 양초, 2단에는 K-1개의 양초, …, K단에는 1개의 양초를 배치해서 총 (K(K+1))/2개의 양초가 필요하다.

당신이 사용할 양초의 개수 N이 주어질 때, 이 양초를 모두 사용하면 몇 단 크기의 촛불 삼각형을 만들 수 있는지 구하여라.

입력

첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에 양초 개수가 주어진다. (1≤N≤1018)

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

각 테스트 케이스 마다 주어진 양초 N개를 모두 사용하여 만들 수 있는 촛불 삼각형의 단수를 출력한다. 만약 삼각형을 만드는 것이 불가능하면 -1을 출력한다.

---

풀이방법

• 이분탐색
• (K(K+1))/2 값이 N과 일치하는 경우 K 출력
• L > R이 되었을 때까지 일치하지 않는 경우 -1 출력

Code

package lab5;

import java.util.Scanner;

public class 촛불이벤트 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int TC = sc.nextInt();
		for (int tc = 1; tc <= TC; tc++) {
			sb.append("#" + tc + " ");
			
			long L = 1;
			long R = 10000000000L;
			long n = sc.nextLong();
			
			while (L <= R) {
				long mid = (L + R) / 2;
				long k = mid * (mid + 1) /2;
				if (k < n) {
					L = mid + 1;
				} else if (k > n) {
					R = mid - 1;
				} else {	// k == n
					sb.append(mid);
					break;
				}
			}
			if (L > R) {
				sb.append(-1);
			}
			sb.append("\n");
		}
		System.out.print(sb);
	}
}

참고

System.out.println(sb); 했더니 tc 1개 안맞음