1. 문제설명

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

2. 입/출력

입력
- 디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones
- 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k
출력
- 최대 몇 명까지 징검다리를 건널 수 있는지 return
제한사항
- 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한
- 1 <= len(stones) <= 200,000
- 1 <= stones[i] <= 200,000,000
- 1 <= k <= len(stones)

3. 문제 분류

Binary Search

4. 알고리즘 설계

모든 디딤돌을 하나씩 깎아보았다

최적화 케이스에서 당연히 시간초과ㅋㅋㅋ

int decrease(vector<int>& stones) {
    int cnt = 0, ret = 0;
  
    for (int& cur : stones) {
        cur--;
        if (cur <= 0) {
            cnt++;
            ret = max(ret, cnt);
        }
        else cnt = 0;
    }
  
    return ret;
}
  
int solution(vector<int> stones, int k) {
    int answer = 1;
    int len = stones.size();
  
    while (true) {
        int cnt = decrease(stones);
        if (cnt >= k) break;
        answer++;
    }
  
    return answer;
}

이런 문제의 경우 O(lgN), O(N) 알고리즘 사용이 가능하다.
- O(N) : for문 한줄로 값을 계산할 수 있을 거 같지 않았다.
- `O(lgN) : 우선순위 큐와 이분 탐색…
  - 우선순위 큐는 징검다리 순서가 보장되어야 하니까 패스
  - 남은 건 이분 탐색이다!
  - 물론, 생각해보면 이분 탐색 문제이긴 하다.
탐색
- 어떤 값을 left, right로 설정할 수 있을까?
  - 징검다리를 밟을 때마다 한칸씩 줄어들기 때문에 k의 제한이 없다면 가장 큰 원소의 수만큼 지나갈 수 있을 것이다.
    - stones의 가장 큰 원소만큼 지나갈 수 있다!
  - 모든 칸은 1이상이 보장되므로, left는 stones의 가장 작은 원소로 잡는다.
- mid는 N명의 사람이 지나갈 수 있는가?에 대한 값이 될 것이다.
- k 제한을 어떻게 검사할 수 있을까?
  - 문제를 보고 간단히 생각해보면 0인 칸의 이어진 개수가 k보다 작으면 된다.
  - 디딤돌의 값이 mid값보다 작다면 반드시 0이 될 것이다.
    - 사람이 밟을 때마다 1씩 감소하기 때문에!

5. 전체 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> v;
int K;

bool check(int mid) {
	int cnt = 0;

	for (auto& nxt : v) {
		if (nxt < mid) cnt++;
		else cnt = 0;

		if (cnt >= K) return false;
	}

	return true;
}

int solution(vector<int> stones, int k) {
	int ans, left, right, mid;

	tie(ans, left, right, K) = 
		make_tuple(0, *min_element(stones.begin(), stones.end()), *max_element(stones.begin(), stones.end()), k);
	v.assign(stones.begin(), stones.end());

	while (left <= right) {
		mid = (left + right) / 2;

		if (check(mid)) {
			left = mid + 1;
			ans = max(ans, mid);
		}
		else right = mid - 1;
	}

	return ans;
}

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

1. 문제설명

2. 입/출력

3. 문제 분류

4. 알고리즘 설계

5. 전체 코드