99클럽 코테 스터디 2일차 TIL (미들러): [백준][Java] 11561 징검다리 - 실버3

 

문제 보기

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

 

 

풀이

연속해서 이분탐색 문제가 나왔다.

그러나 오늘은 처음부터 이분탐색이라는 걸 알아차리지 못했다.

오히려 처음엔 DP 문제 아니야? 하고 풀이 방법을 잘 생각해보다가 뭔가 의문점을 발견한 것이다.

 

당연히 1부터 시작해서 1씩 더하는 게 맞는 답 아닌가?

 

그렇게 while (sum <= n) sum += i++; ...같은 코드를 짜다 보니 10^16이 얼마나 큰 수 일까 관심이 갔다.

 

시간 초과 날 것 같은데 다른 방법은 없을까?

 

 

어김없이 구글 선생님한테 물어봤다.

블로그 선생님들이 고등학생 때 배워 놓고 까~맣게 잊어버린

등차 수열의 합이 내가 찾으려는 것이었다.

 

1. 등차 수열의 합

결론부터 말하자면 등차수열의 합 공식은 위와 같다.

• S 합
• n 마지막 항(항의 수)
• a 첫 항
• l 일반 항

우리가 구하려는 수열은 1부터 1씩 증가하기 때문에 l = n으로 봐도 된다.

또한 a는 1이다.

 

sum = n * (n + 1) / 2

 

 

2. 이분 탐색

이제 간단하게 구할 수 있는 식을 만들었으니 이 n이 얼마일지 유추하면 된다.

물론 10^16은 매우매우 큰 수이기 때문에 이분 탐색을 이용할 것이다.

  long N = Long.parseLong(br.readLine());
  long low = 1;
  long high = Integer.MAX_VALUE;
  long max = 0;
  while (low <= high) {
    long mid = (low + high) / 2;
    long num = mid * (mid + 1) / 2;

    if(num <= N){
      max = Math.max(max, mid);
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

 

또 lower bound 이분 탐색이니 저번 포스트를 또 또 첨부 하겠다.

https://mountain-noroo.tistory.com/205

[백준][Java] 19637 IF문 좀 대신 써줘 - 실버3

 

3. high를 Integer.Max_VALUE로 한 이유

위 코드에서 의문이 들 수 있다.

10^16은 int의 범위를 넘어가는데 high를 저렇게 설정 해도 되나?

 

그러나 10^16이 입력으로 들어왔을 때의 최대 징검다리 값을 생각 해보자.

위 공식을 n으로 전개 해보면 n^2 + n = 10^16 * 2가 될 것이다.

여기서 n에 Integer.Max_VALUE를 대입 해봤을 때 좌항이 우항보다 더 컸기 때문에 high를 해당 값으로 잡은 것이다.

 

 

전체 코드

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

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int T = Integer.parseInt(br.readLine());
    while (T-- > 0) {
      long N = Long.parseLong(br.readLine());
      long low = 1;
      long high = Integer.MAX_VALUE;
      long max = 0;
      while (low <= high) {
        long mid = (low + high) / 2;
        long num = mid * (mid + 1) / 2;

        if(num <= N){
          max = Math.max(max, mid);
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }

      bw.write(max + "\n");

    }
    bw.flush();
    bw.close();

  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Silver/11561.%E2%80%85%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC

CodingTest_AutoSave/백준/Silver/11561. 징검다리 at main · MetroDefro/CodingTest_AutoSave