99클럽 코테 스터디 2일차 TIL + 백준1072 징검다리

문제

승택이는 강을 건너려 한다.

승택이는 수영을 못하기 때문에, 강에 놓인 징검다리를 밟고 건너갈 것이다.

승택이는 수영은 못하지만 제자리뛰기는 정말 잘한다. 원하는 어느 곳으로든지 점프해서 바로 갈 수가 있다.

승택이는 이제 강의 한쪽 변 앞에 서 있다.

강엔 1번부터 시작해 2번, 3번, ... , N번 징검다리가 차례대로 놓여 있다.

강의 폭이 넓은 탓에 징검다리의 수는 엄청나게 많다.

이 징검다리를 모두 밟고 싶지는 않았던 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만을 밟고 가기로 했다.

물론 강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너기 위해 승택이는 다음과 같은 규칙을 정했다.

1. 첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.
2. 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
3. N번 징검다리는 반드시 밟아야 한다.
4. N번 징검다리를 밟은 후 강 건너로 이동할 땐 점프를 하지 않으므로 위의 규칙이 적용되지 않는다.

승택이가 위의 규칙을 지키며 강을 건널 때, 밟을 수 있는 징검다리의 최대 수는 몇 개일까?

 

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 정수 한 개로 이루어져 있으며, 징검다리의 총 수 N을 의미한다. (1 ≤ N ≤ 1016)

 

출력

각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다.

 

 

어제 풀었던 문제와 비슷하게 이분 탐색에 관한 알고리즘이다. 징검다리 건너는데 한번에 건널 수도 있는 승택이가 대단하긴 한데, 결국 밟을 수 있는 최대 징검다리 이기 때문에 1+2+3+......+k <= N 인 셈이다(등차수열의 합 <= N) 

등차수열의 합이 N보다 작은 최대 자연수 k를 찾는 문제이기 때문에 이분 탐색으로 어제와 비슷하게 시간을 줄이는 방법을 사용했다. 

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int testCase = scanner.nextInt();

        long[] arr = new long[testCase];

        for(int i=0;i<testCase;i++){
            arr[i] = findMax(scanner.nextLong());
        }

        for(int i=0;i<testCase;i++){
            System.out.println(arr[i]);
        }
        scanner.close();
    }

    public static long findMax(long n){
        long left = 1,right = n;
        long result = 0;

        while(left<=right){
            long mid = (left+right)/2;

            if( mid > (2*n)/(mid+1)){ // sum 의 값이 long 자료형 보다 커져 오버플로우가 생길 수도 있으니 미리 검사
                right = mid -1;
                continue;
            }

            long sum = mid * (mid+1) / 2;

            if(sum <= n){
                result = mid;
                left = mid + 1;
            }else {
                right = mid -1;
            }
        }
        return result;
    }
}

 

---

 

왜 자꾸 틀렸는지 곰곰히 생각을 해보다가 등차수열의 합을 구하는 공식에 곱하기 연산이 있는걸 보니 long자료형인데 오버플로우가 발생하나? 해서 오버플로우를 검사하는 조건문을 하나 추가했다. 옛날에 정수는 무조건 int형으로하다가 자꾸 오버플로우가 발생해서 이젠 범위를 확인하고 long을 쓰는것이 습관이 되었는데 곱셈 계산이 끼어있으니 그래도 오버플로우가 발생하는구나..