징검다리 43236

문제

첫 번째 접근 방법

2	11	14	17	21

가장 먼저 치워야 할 것은 2일 것이다.
바위 사이의 거리와 바위의 거리, 2개를 묶어서 생각하면 어떨까 싶었다.

2	11	14	17	21
2	9	3	3	4

이렇게 말이다.

2	14	17	21	11
2	3	3	4	9

묶고서 바위 사이의 거리로 정렬해준다.

14	17	21	11
3	3	4	11

지우고 병합한다.

21	17	11
4	6	11

지우고 병합한다.
문제가 있다. 매번 정렬을 해줘야 하고 병합하려면 뒤의 값을 찾아야 한다.
매우 많은 시간을 사용할 것 같다.

왜 예제에서는 2, 14를 줬을까?

0	2	11	14	17	21	25

거리를 계산한다면 이럴 것이다.
앞에서부터 거리의 최솟값 4를 더한다고 생각해보자.

0	2	11	14	17	21	25
4	6	15	18	21	25	29

0, 2, 11은 다음 위치에 해당하는 값보다 크다. 하지만 0은 시작점이므로 지울 수 없다.
그렇다면 2, 11인데 n=2에 부합하므로 앞에서부터 세어주면 될 것 같았다.

첫 번째 실패

돌을 제거해주는 것을 작성해주지 않아서 그런지 실패했다.

두 번째 접근 방법

돌을 직접 제거해줘야 하나 싶었다. 그거로 골머리를 썩이다가 다른 사람 풀이를 봤더니 그냥 갱신해주는 방식으로 해결했던 것을 봤다. 막상 이런 것들 보면 간단한데 왜 자꾸 생각나지 않는 걸까 싶기도 하다.

코드

#include <vector>
#include <algorithm>
using namespace std;
int solution(int distance, vector<int> rocks, int n)
{
    int answer = 0, high, mid, low = 0;
    sort(rocks.begin(), rocks.end());
    high = rocks[rocks.size() - 1];
    rocks.push_back(distance);
    while (low <= high)
    {
        mid = (low + high) / 2;
        int cnt = 0, rockPos = 0;
        for (int i = 0; i < rocks.size(); ++i)
            if (rocks[i] - rockPos < mid)
                ++cnt;
            else
                rockPos = rocks[i];
        if (cnt > n)
        {
            high = mid - 1;
        }
        else
        {
            answer = mid;
            low = mid + 1;
        }
    }
    return answer;
}

풀이

막상 풀고 나면 간단한데 풀기 전에는 어려운 느낌이 든다. 요즘 문제를 풀면 풀수록 간단하게 봐야 할 부분을 너무 복잡하게 봐서 못 푸는 것 같다. 좀 더 간단하게 보는 연습을 해야겠다.