[programmers/kakao] 징검다리 건너기

문제

출처 : https://programmers.co.kr/learn/courses/30/lessons/64062?language=java 

코딩테스트 연습 - 징검다리 건너기

징검다리에 돌이있다. 이 돌에는 밟을수있는 횟수가 정해져있으며, 한번 밟을때마다 횟수가 줄어든다.

또한, 징검다리를 건너뛸수있는 최대 길이 k 가 주어진다.

한 사람이 징검다리를 한번 건널때 밟을 수 있는 모든 돌을 밟는다 했을때, 최대 몇명의 사람이 징검다리를 건널 수 있는지 구하는 문제다.

---

문제를 읽어보면, "밟을 수 없는돌의 연속길이가 k가 되는지점"을 구하는 문제임을 알수있다.

징검다리의 길이가 200,000 이기때문에, 완전탐색으로 구할경우 O(징검다리길이^2)번 반복하게되어 시간초과가 나온다.

문제를 풀기위해서 결정문제를 사용했다. 

 

알고리즘은 간단한데,

현재 A만큼 건넜을때, 다음사람이 돌을 건널수있는가?

-> 건널수있다 : left = A+1

-> 건널수없다 : right = A-1

 

위 과정을 반복하면 된다.

주요 소스코드

    public int solution(int[] stones, int k) {
        int left = 0, right = 2000000000;
        int maximumCrossCount = 0;
        for(int i = 0; i < 64; i++){
            int crossCount = (left + right) / 2;
            if(this.isCrossable(k, crossCount, stones)){
                maximumCrossCount = max(maximumCrossCount, crossCount);
                left = crossCount+1;
            }
            else right = crossCount-1;
        }
        return maximumCrossCount;
    }

(2^64)번 반복하면 mid의 오차범위가 1/(2^64)만큼되서 범위가 2^64보다 큰 경우를 제외하면 항상 답이 나온다. (범위가 더 필요할경우 늘리면됨) 

나는 이 방식이 편해서 이렇게 구현하는데, while(left < right)로 구하는게 더 빠르긴하다. 기호에 따라 구현하도록하자

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/kakao%20%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%20%EA%B1%B4%EB%84%88%EA%B8%B0/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃