징검다리 건너기

코드

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>

using namespace std;

int making_map(map<int, int> &m, int index, int max, int k) {
    int left = index - 1, right = index + 1;
    m[index] = k - 1;
    if (right == max) {
        if (m.find(left) != m.end()) {
            m[left]--;
            int dist = k - m[left];
            m[index] = m[index - dist + 1] = m[left];
        }
    }
    else if (left < 0 ) {
        if (m.find(right) != m.end()) {
            m[right]--;
            int dist = k - m[right];
            m[index] = m[index + dist - 1] =  m[right];
        }
    }
    else {
        if (m.find(left) != m.end() && m.find(right) != m.end()) {
            int left_member = k - m[left] , right_member = k - m[right];
            int far_left = left - left_member + 1, far_right = right + right_member - 1;
            int new_member = left_member + right_member + 1;
            m[index] = m[far_left] = m[far_right] = k - new_member;
        }
        else {
            if (m.find(left) != m.end()) {
                int far_left = left - (k - m[left]) + 1;
                m[left]--;
                m[index] = m[far_left] = m[left];
            }
            if (m.find(right) != m.end()) {
                int far_right = right + (k - m[right]) - 1;
                m[right]--;
                m[index] = m[far_right] = m[right];
            }
        }
    }
    return m[index];
}

int solution(vector<int> stones, int k) {
    int answer = 0;
    //pair< value, index>
    vector<pair<int, int>> _stones; _stones.reserve(stones.size());
    for (int i = 0; i < stones.size(); i++) {
        pair<int, int> temp (stones[i],i);
        _stones.push_back(temp);
    }
    sort(_stones.begin(), _stones.end());
    map<int, int> m;

    for (int i = 0; i < _stones.size(); i++) {
        answer = _stones[i].first; 
        int ret = making_map(m, _stones[i].second, _stones.size(), k);
        if (ret <= 0) return answer;

    }
    return answer;
}

int main() {
    vector<int> stones = {1,2,3,4,5,6,7,8 };
    int k = 8;
 
    cout << solution(stones, k);

}