99클럽 코테 스터디 14일차 TIL, 프로그래머스 / 징검다리

 

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

 

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

using namespace std;


int solution(int distance, vector<int> rocks, int n) 
{
    int answer = 0;
    int minD = 1, maxD = distance;
    sort(rocks.begin(), rocks.end());
    
    // for (int rock : rocks) cout << rock << ",";
    cout << distance << endl;
    
    while(minD <= maxD)
    {
        int removeCnt   = 0;
        int curD        = (minD + maxD) / 2;
        int prevRock    = 0;
        
        // curD : 거리의 "최소값" 중에 최대값
        // 이제 rock 을 빼보면서, 정말 해당 curD 가 거리의 "최소값" 이 되는지를 판단
        // 만약 된다면, 더 큰 값을 찾아나서고, 아니라면 더 작은 값을 찾아나선다.
        // 즉, curD 값보다 크거나 같은 "거리" 만 존재할 수 있도록 바위들을 제거한다.
        
        for (int i = 0; i < rocks.size(); ++i)
        {
            if (rocks[i] - prevRock < curD) // 제거 
                removeCnt += 1;
            else                            // 제거 X
                prevRock = rocks[i];
        }
        
        // 도착점, 마지막 바위 거리 고려
        if (curD > distance - prevRock)
            removeCnt += 1;
        
        cout << removeCnt << "," << curD << endl;
        
        if (removeCnt <= n) // 조건 만족 
        {
            // 거리의 최소값을 curD 로 맞출 수 있는 경우이다.
            
            // Q1. 제거 이후, curD 보다 큰 값만 만날 수 있는 거 아닌가 ?
            // ex) curD 가 3인데, 거리가 '2' 여서, 돌을 제거했더니, 중간 거리가 4일 수도 있다.
            //     이때는 curD 가 거리의 최소값이 아닐 수도 있자나.
            // no. 예를 들어 아래를 보자
            // n == 2, curD = 3
            // 0(s) 2 4 6 8 10(e)
            //      x   x x
            // 즉, 실제 뺀 rock 은 3개 이므로, n 을 초과하여 해당 케이스로 고려되지 않는다.
            
            // Q2. removeCnt < n 인 경우는 왜 고려하는 거지 ?
            // curD 가 너무 작다는 의미아닌가 ? 그러면 그냥 minD = curD + 1 만 하고 break 하면 안됨 ?
            // 흐음... 모르겠다. 일단 넘어가기
            // n == 2, curD = 3
            // 0(s) 2,11,14,17,21,25(e)
            //      x      (removeCnt == 1)
            answer = max(answer, curD);
            minD = curD + 1;
        }
        else 
        {
            // 조건 만족 X. curD 가 "최소값" 이기에는 너무 큰 값.
            // curD. 즉 거리의 최소값을 줄여서 돌을 덜 제거하고자 한다.
            maxD = curD - 1;
        }
    }
    
    return answer;
    
    
}