[프로그래머스] 2019 카카오 개발자 겨울 인턴십 - 징검다리 건너기, C++

https://programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

본 문제는 주어진 징검다리를 최대 몇명이 건널 수 있는지 구하는 문제다. 문제의 조건은 다음과 같다.

1. 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어든다.
2. 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있다.
3. 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있다.
4. 여러 칸을 건너 뛸 경우 k를 넘을 수 없다.

제한사항은 다음과 같다.

1. 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주한다.
2. stones 배열의 크기는 1 이상 200,000 이하
3. stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수

따라서 1명씩 징검다리를 건너서 가능한 경우를 확인하는 방법은 너무 오래걸린다. 그렇기 때문에 1명이 아닌 단체로 징검다리를 건너는 경우로 바꿔 생각해야한다. 즉 이분 탐색을 이용하면 문제를 해결할 수 있다.

#include <string>
#include <vector>
 
using namespace std;
 
bool cal(int num, vector<int> stones, int k) {
    int jump = 1;
    for (int i = 0; i < stones.size(); i++) {
        // 단체로 건널경우 디딤돌의 크기가 0이하가 되면 한 칸 더 건너 뛰어야 한다.
        // 그게 아닐경우 1칸씩 뛴다.
        if (stones[i] - num <= 0) jump += 1;
        else jump = 1;
        
        // 건너 뛰는 크기가 k를 넘어서는 안된다.
        if (jump > k) return false;
    }
    return true;
}
 
int solution(vector<int> stones, int k) {
    
    // 디딤돌 각각의 크기가 1 이상 200000000이하 이므로
    // 1명 이상 200000000이상이 건너는 경우를 이분 탐색 하면된다.
    int left = 1, right = 200000000;
    while (left <= right) {
        int mid = (right+left)/2;
        
        // 단체로 건널 수 있는지 확인
        if (cal(mid, stones, k)) left = mid+1;
        else right = mid-1;
    }
    
    return left;
}