99클럽 코테 스터디 2일차 TIL - 백준[11561]

---

문제 풀이

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

문제
승택이는 강을 건너려 한다. 승택이는 수영을 못하기 때문에, 강에 놓인 징검다리를 밟고 건너갈 것이다.
승택이는 수영은 못하지만 제자리뛰기는 정말 잘한다. 원하는 어느 곳으로든지 점프해서 바로 갈 수가 있다.
승택이는 이제 강의 한쪽 변 앞에 서 있다. 강엔 1번부터 시작해 2번, 3번, ... , N번 징검다리가 차례대로 놓여 있다.
강의 폭이 넓은 탓에 징검다리의 수는 엄청나게 많다.
이 징검다리를 모두 밟고 싶지는 않았던 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만을 밟고 가기로 했다.
물론 강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너기 위해 승택이는 다음과 같은 규칙을 정했다.

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

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

입력
첫째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 정수 한 개로 이루어져 있으며, 징검다리의 총 수 N을 의미한다. (1 ≤ N ≤ 1016)

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

나의 풀이

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
    
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int testCase = Integer.parseInt(br.readLine());
        
        for (int i=0; i<testCase; i++) {
            long stones = Long.parseLong(br.readLine());
            long start = 0;
            long last = (long) Math.sqrt((2*stones-1));
            long result = 0;
            
            while (start <= last) {
                long mid = (start+last)/2;
                long sum = (mid)*(mid+1)/2;
                if (sum <= stones) {
                    result = Math.max(mid,result);
                    start = mid + 1;
                } else {
                    last = mid-1;
                }
            }
            
            bw.write(result+"\n");
        }
        br.close(); 
        
        // 최종 출력
        bw.flush();
        bw.close();
    }
}

해결과정

1. 루프돌리기, 한 심사위원만 사용하여 최소시간으로 끝낼수 있는 경우 배열 sorting
2. 최대값으로 한 심사위원만 사용하여 최소시간으로 끝낼수 있는 경우 대입
3. 이분탐색 시도 중간값, 해당시간때 발생할수 있는 사람수 변수 선언
4. 시간때별로 발생할수 있는 사람 경우 변수 대입
5. 최소값, 최대값 범위차이 끝까지 줄이기
6. 이분탐색이 더 불가한경우에 반환

---

오늘 배운 점

이분 탐색을 할 때는

1. 내가 찾아야 할 정답의 범위를 left ~ right로 정한다.
2. 정답을 mid로 간주한 후, 해당 정답이 유효한지 살펴본다.
3. 2번 여부를 따지며 left와 right의 범위를 좁힌다.
4. left > right가 되면 반복을 끝내고 답을 반환한다.

import 를 까먹지말자

• java로 코테를 하는게 처음이라, import 를 하지 않아서 자꾸 런타임 오류가 났는데 원인을 몰라 헤맸다.