[랜덤 마라톤] 슬라임 잡고 레벨 업!(29717)

1. 문제 풀이 아이디어

• 등차수열의 합을 구하는 식과 이분 탐색을 사용하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int t = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < t; i++) {
            long n = Long.parseLong(bufferedReader.readLine());
            long exp = n * (n + 1) / 2;
            long s = 1, e = 1000000000;
            while (s < e) {
                long m = (s + e) / 2;
                long nexp = m * (m + 1);
                if (nexp <= exp) {
                    s = m + 1;
                } else {
                    e = m - 1;
                }
            }
            stringBuilder.append(s).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

3. 정리

• 입력받은 n을 등차수열 합 공식에 넣어 필요한 경험치 exp를 계산한다.

• 이분 탐색을 활용해 해당 경험치를 만족하는 최소 레벨을 찾는다.

• 경험치 exp와 비교하여, 만약 m에서의 경험치가 exp보다 작거나 같으면, s를 m + 1로 설정하여 더 높은 범위를 탐색한다.

• 그렇지 않다면 e를 m - 1로 줄여 낮은 범위를 탐색해 나가며 반복한다.

• 최종적으로 s 값을 구한 후, 결과를 출력한다.