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

문제 링크

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

 

 

 

풀이

이분탐색 문제였다.(구글링해서 앎)

 

// 요약

1) 처음에 최대값, 최소값을 구한다.

 

2) 최소값이 최대값과 같아질 때까지 반복문을 돈다.

중간값은 (최소값+최대값)이 홀수일 때는 2로 나누고 +1, 짝수일 때는 2로만 나눈 값이다

(가능한 최대값을 기준으로 진행)

(stones의 원소 - 중간값)이 음수가 연속으로 K번 이상으로 나올 때 최대값을 중간값으로 갱신

(stones의 원소 - 중간값)이 음수가 연속으로 K번 미만 나올 때, 최소값을 중간값으로 갱신

대신, 최대값을 갱신할 때는 불가능했던 값이므로 중간값-1로 갱신 해준다.

 

3) answer에 최소값 혹은 최대값을 넣어준다(두 값이 같음)

 

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

// 디딤돌의 숫자는 한 번 밟을 때 1씩 줄어듦
// 디딤돌이 0이 되면 더 이상 밟기 X
// 그 다음 디딤돌로 한 번에 여러 칸을 건너 뜀(대신 무조건 가장 가까운 디딤돌로 가야됨)
// 한 번에 한 명씩

// 디딤돌의 최대 칸수 K(K미만으로 뛰어야함)
// 디딤돌 숫자가 순서대로 담긴 배열 stones

int solution(vector<int> stones, int k) {
    int answer = 0;
    
    // 이분 탐색을 위한 최대, 최소값 init
    int maxNum, minNum;     // 최대, 최소값
    minNum = maxNum = stones[0];
    for(int i=1; i<stones.size(); i++){
        minNum = min(minNum, stones[i]);
        maxNum = max(maxNum, stones[i]);
    }
    
    // 최소값과 최대값이 같아질 때까지 이분탐색
    while(minNum != maxNum){
        // 중간값
        int midNum = minNum + maxNum;
        midNum = midNum%2==0 ? midNum/2 : midNum/2+1;
        
        // 진행
        int count=0;
        bool check=true;
        for(int i=0; i<stones.size(); i++){
            count = stones[i]-midNum < 0 ? count+1 : 0;
            if(count<k) continue;       // count 개수가 k 미만이면 진행
            check = false;
            break;
        }
        if(check) minNum = midNum;      // 건널 수 있으므로 가능한 최소값
        else maxNum = midNum-1;         // 징검다리를 못 건너므로 -1
    }
    answer = minNum;
    
    return answer;          // 최대 몇 명 건널 수 있는지
}