[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기(C++)

문제 제목

 

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

 

 

문제 설명

 

 - 카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 징검다리를 건너려 한다.

 

 - "라이언" 선생님은 징검다리를 무사히 건너기 위해 다음과 같은 규칙을 만들었다.

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.

• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.

• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

 

 - "니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며,

   한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작한다.

 

 - 최대 몇 명 까지 징검다리를 건널 수 있는지 반환하라.

 

---

 

입력 값

 

 - 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한이다.

 

 - 디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones의 크기는 1이상 200,000 이하이다.

 

 - stones 배열 각 원소들의 값은 1 이상 2억 이하인 자연수이다.

 

 - 디딤돌의 최대 칸수 k는 1 이상 stones 길이 이하인 자연수이다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 디딤돌에 적힌 숫자는 최대 2억이다. 즉, 2억명이 징검다리를 건너게 되면, 그 다음 부터는 k 값과 상관 없이 무조건 건널 수 없다.

 

 - 1 ~ 2억 사이에서 해당 번째 사람이 건널 수 있는지 판단하면 된다.

 

 -  2억명을 모두 순서대로 탐색하기엔 시간이 부족하고, 비 효율적이기 때문에 이분 탐색을 이용하여 빠르게 탐색한다.

 

 - 이분 탐색을 이용하여 중간 값 번째의 사람이 건널 수 있다면, 그 이하의 값은 탐색할 필요가 없다.(건널 수 있는 최대 명수가 필요)

   건널 수 있다면, 해당 값보다는 큰 값들 중 건널 수 있는 값을 찾는다.

 

---

소스 코드

 

#include <bits/stdc++.h>


using namespace std;

bool stonesSum(vector<int> &stones, int k, int mid)
{
	int sum = 0;
	for (int i = 0; i < stones.size(); i++)
	{
		if (stones[i] - mid < 0)
		{
			sum++;

			if(sum >= k)
				return false;

		}
		else
		{
			sum = 0;
		}
		
	}
	return true;
}


int solution(vector<int> stones, int k) {
	int answer = 0;

	int maxNum = 200000000;
	int minNum = 1;

	

	while (maxNum >= minNum)
	{
		int mid = (maxNum + minNum) / 2;
		if (stonesSum(stones, k, mid))
		{
			answer = mid;
			minNum = mid + 1;
		}
		else
		{
			maxNum = mid - 1;
		}


		
	}

	return answer;
}