[프로그래머스] 징검다리 건너기 (C++)

문제 링크: programmers.co.kr/learn/courses/30/lessons/64062

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

1. 주의할 점

- 숫자가 크다 → 단순한 풀이로 접근하려고 하면 TLE가 발생한다

- 벡터/배열의 index 범위를 벗어나는지 확인한다

 

2. 구현

- 이분탐색을 통해 접근한다. 중간값만큼의 사람들이 넘어갈 수 있는가?

- 돌의 가장 큰 크기가 200,000,000이므로 이보다 1 더 크게 R을 설정한다. L은 0으로 설정한다

- 0번째 돌까지 뛰는것도 1만큼 뛴것이기 때문에 idx를 -1로 설정하고 점프 크기(J)를 1~K까지로 설정한다

- 현재 위치에서 뛰어서 징검다리의 반대편까지 뛸 수 있다면, 현재 위치를 옮긴다

- 현재 위치에서 1~K까지의 거리 중에서 Mid만큼이 뛸 수 있는 돌이 있다면 점프한 돌로 현재 위치를 옮긴다

- 만약 Mid명만큼 이동이 가능하다면 Mid의 크기를 키우고, 불가능하다면 Mid의 크기를 줄이는 식으로 진행한다

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    int len = stones.size();
    int l=0,r=200000001,mid,result;
    while(l<=r){
        mid = l+(r-l)/2;
        bool avail=true;
        int idx=-1;
        while(idx<len){
            bool temp=false;
            for(int j=1;j<=k;j++){
                if(idx+j==len){
                    temp=true;
                    idx+=j;
                    break;
                }
                int next = stones[idx+j];
                if(next>=mid){
                    temp=true;
                    idx+=j;
                    break;
                }
            }
            if(!temp){
                avail=false;
                break;
            }
        }
        if(avail){
            answer = mid;
            l = mid+1;
        }
        else r = mid-1;
    }
    return answer;
}