[C/C++] Lv3 프로그래머스 - 징검다리 건너기

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

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

- 접근법

사람 한명이 지날 때 마다 배열의 각 요소가 1씩 감소된다. 그렇게 여러명이 지나가게 되면 결국 언젠가 그 요소는 0이 되고 그 돌을 무시하고 지나갈 수 있는 최대 거리는 k로 주어진다.

즉 사람이 지나갈 때 마다 배열의 각 요소가 1씩 감소되고 결국 0이 되어버린 돌들을 다음 사람이 0이 된 돌들을 최대 k개 만큼 무시하고 지나갈 수 있는 최대 사람 수를 구하는 것이다.

 

가장 쉽게 생각할 수 있는 방법은 사람1명부터 +1하면서 못지나갈때까지 탐색하는 것인데 각 배열의 원소값이 2억까지 주어진다는 것은 답이 2억명이 될수도 있다는 것이다.

그러므로 시간 내에 해결할 수 있는 해법이 아니다.

 

그렇다면 어떻게 접근해야할것인가?

 

결국 문제의 요구사항은 최대 지나갈 수 있는 사람의 수를 구하는 것이다.

예를 들어 4명의 사람이 징검다리를 무사히 건넜다는 것은 무엇을 의미하는 것일까?

바로 1,2,3명의 사람이 그 징검다리를 지나고 무사히 건널 수 있다는 것이다.

그렇다면 7명의 사람이 그 징검다리를 건널 수 없다는 것은 무엇을 의미할까?

그것은 7명 이상의 사람은 그 징검다리를 절대 건널 수 없다는 것이다.

 

쉽게 말해 x명의 사람이 그 징검다리를 건널 수 있다면 1~x명까지 모두 건널 수 있다는 것이고. (left)

x명의 사람이 그 징검다리를 건널 수 없다면 x~무한대 명까지 모두 건널 수 없다는 것이다. (right)

 

이것은 즉 이분탐색으로 최적의 x명을 찾을 수 있다는 것이다.

(mid) 만큼의 사람 수가 징검다리를 건널 수 있었다면 right로 보내 더 큰 (mid) 만큼의 사람 수가 건널 수 있는 지 탐색하고 (mid) 만큼의 사람 수가 징검다리를 건널 수 없었다면 left로 보내 좀 더 작은 (mid) 만큼의 사람 수가 건널 수 있는 지 탐색하면 쉽게 답을 구할 수 있다.

 

따라서 최대 O(20만*log(2억)) 로 해결가능하다.

---

- 소스코드

#include <string>
#include <vector>
#define MAXI(A,B) A>B ? A : B
using namespace std;
int board[200002];
int n_size;
bool checking(int n,int k) { // n명이 지나갈 수 있는 지 검사
    int count=0;
    for(int i=0;i<n_size;i++) {
        if(board[i]-n<0) {
            count++;
            if(count==k) return false;
        }
        else {
            count=0;
        }
    }
    return true;
}
int solution(vector<int> stones, int k) {
    int answer = 0;
    int start=0,end,mid;
    bool flag;
    n_size=stones.size();
    for(int i=0;i<n_size;i++) {
        end=MAXI(end,stones[i]);
        board[i]=stones[i];
    }
    while(start<=end) {
        mid=(start+end)/2;
        flag=checking(mid,k);
        if(flag) {
            answer=MAXI(answer,mid);
            start=mid+1;
        }
        else {
            end=mid-1;
        }
    }
    return answer;
}