[TIL] 99클럽 코테 스터디 2일차 TIL + 등차수열의 합

 

문제 풀이 (백준 11561 징검다리)

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

문제 탐색하기

문제 풀이 방식 접근

징검다리를 건너는 규칙을 살펴보면 두번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다고 되어있습니다.

이를 통해 등차수열의 합 공식을 활용해서 문제를 풀어야한다는 것을 알 수 있습니다.

등차 수열의 합이 총 징검다리의 개수보다 작거나 같을 경우의 값 = 밟을 수 있는 징검다리의 최대 개수라는 점을 고려하여 문제를 풀면 됩니다.

 

* 등차수열 합 공식?

등차수열 합 공식 : n(n+1)/2

등차수열의 합 공식을 통해서 징검다리가 10개인 경우와 11개인 경우를 예시로 들어보겠습니다.

 

[ 징검다리의 개수 : 10 ]

 

징검다리의 개수가 10개인 경우는 1, 3, 6, 10 번째 징검다리를 밟아서 총 4번이 밟을 수 있는 징검다리의 최대 개수 입니다.

 

[ 징검다리의 개수 : 11 ]

 

징검다리의 개수가 11개인 경우는 1, 3, 6, 11 번째 징검다리를 밟아서 총 4번이 밟을 수 있는 징검다리의 최대 개수 입니다.

 

시간 복잡도 탐색

N이 최대 10의 16승까지 주어질 수 있어서 순차탐색을 적용하기에는 시간초과될 수 있습니다.
밟을 수 있는 징검다리의 최대 개수를 구하기 위해 1부터 주어진 범위까지를 탐색하는 것이다보니 정렬된 배열을 탐색하는 것과 같습니다. 따라서 이분탐색을 활용하여 N(logN) 의 시간복잡도를 적용하여 문제를 풀 수 있습니다.

 

* 이분탐색 적용

N이 나오게하는 등차수열의 합의 변수 n의 최대값을 구하기 위해 이분탐색을 적용했습니다.

left값이 right 값보다 커졌을 때까지 이분탐색을 반복하는데 반복문이 끝났을때에는 left값이 right값보다 크기 때문에 n의 최대값을 구하기 위해서는 -1을 해줘야합니다.

 

이분탐색에 대한 개념은 앞 글에서 다뤘으니 참고하시려면 아래의 링크로 이동해주세요!

https://coding-babo.tistory.com/148

[TIL] 99클럽 코테 스터디 1일차 TIL + 이분 탐색

 

 

추가 고려할 점

이분탐색의 범위의 최대값을 10억으로 설정하고 문제 풀이를 진행해야 합니다. 10억보다 큰 값이 들어올 경우 등차수열의 합 공식을 적용할때 곱셈에서 long의 자료형 범위를 초과할 수 있습니다. 또한 10억이면 10의 8승인데 등차수열의 합 공식을 적용해보았을 때 구하려는 n의 값은 10의 8승 보다 큰 수일 수 없기의 이분탐색의 범위를 10억까지 세팅해줄 수 있습니다.

이 부분 때문에 매우 애먹었습니다......

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static long N;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        long[] maxStepArr = new long[T];

        for(int i=0; i<T; i++){
            N = Long.parseLong(br.readLine());
            if(N == 1){
                maxStepArr[i] = 1;
            }else{
                maxStepArr[i] = binarySearch(1, 1_000_000_000L);
            }
        }

        for(long i : maxStepArr){
            System.out.println(i);
        }
    }

    private static long binarySearch(long left, long right){
        long mid = 0;
        long maxStep = 0;

        while(left <= right){
            mid = (left + right)/2;
            maxStep = mid*(mid+1)/2;

            if(maxStep > N){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }

        return --left;
    }
}

 

 

오늘의 회고

등차수열의 합 공식, 이분탐색까지 적용했는데 계속 틀려서 대체 어떤 부분이 문제인 걸까 한참 고민했는데 자료형의 범위를 고려해야한다는 것을 이번기회에 알게되었습니다.. 앞으로 문제를 풀때에는 자료형에 대해서도 좀 더 생각을 해서 문제를 풀어야겠다고 다짐하는 좋은 계기가 된 것 같습니다ㅎㅎ