99클럽 코테 스터디 2일차 TIL - 징검다리 : 백준 11561번 - 이분탐색

1. 오늘의 문제 - 징검다리 : 백준 11561번

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

 

2. 공부한 내용

2 - 1. 규칙 찾기 시도

징검다리가 1개일 때는 최대 징검다리수 는 몇 개 일까?

2개일 때는? 10개 일때는? 

규칙을 찾으려고 노력했다.

 

2 - 2. 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야

1이상 점프해야 한다는 제약 조건은 무엇을 의미할까?

최대한 많은 징검다리를 밟는 걸 찾는 문제다

그러면 정확하게 1칸 뛰고 2칸 뛰고 3칸 뛰는 게 최대한 많은 징검 다리를 밟는 경우의 수일 것이다.

1 이상 뛸 수 있다고해서 처음에 5칸 뛰고 그 다음 7칸 뛰고 그다음 13칸 뛰면 최댓값이 아닐 것이다. 

아주 당연하다.

 

2 - 3. 등차수열의 합

최선의 경우가 1, 2, 3, 4... 뛰는 것이다.

1+2+3+4 했을 때, 입력된 n과 같으면 최댓값이 되지 않을까?

예를 들어, 10개의 징검다리가 있을 때,

1+2+3+4 는 10이다. 따라서, 최댓값은 4

만약, 9개의 징검다리라면 

1+2+3+4 > 9 이고, 1+2+3 < 9 이므로, 최댓값은 3이다.

 

이것을 일반화하면

 

• 등차수열의합 <= n

이것을 만족하는 등차수열의 마지막 값이 최댓값이 되는 것이다.

 

2 - 4. 최대 징검다리 수는 이분탐색으로 찾으면 효율적

입력되는 n의 값은 10의 16제곱이다. 

완전탐색으로 찾으면 엄청 오래걸릴 것이다.

시간 초과가 나겠지?

따라서, 이분탐색으로 찾는다.

3. 풀이

package io.conduktor.demos.dfsbfs.hanghaecote99.middler;

import java.io.*;

// 2. 징검다리 - 백준 : 11561 징검다리
public class Jingumdari2 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        while(t-- > 0) {
            long n = Long.parseLong(br.readLine());
            long left = 0;
            long right = (long) 1e9; // 10억

            long result = 0;

            while (left <= right) {
                long mid = (left + right) / 2;
                long sum = (mid * (mid + 1)) / 2; // 등차수열의 합

                if (sum <= n) {
                    result = Math.max(mid, result);
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            sb.append(result).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

 

4. 소감

규칙을 찾는데 오래 걸렸다.

알고나면 쉬운데, 막상 풀 때는 쉽게 떠오르지 않는 것 같다.

많이 풀면 익숙해지겠지