Programmers - 징검다리 건너기

---

title: Programmers - 징검다리 건너기
date: 2022-09-06
tags:

• Algorithm
• Parametric Search

---

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

문제 요약

사람들이 징검다리를 건너며, 각 돌에 수가 적혀있다.
한 사람이 돌을 밟을 때마다 수가 1씩 줄어들며, 수가 0이 되면 해당 돌은 밟을 수 없다.
최대 k-1개의 돌을 건너뛸 수 있으며, 가장 가까운 돌을 밟아야만 한다.
돌에 적힌 수가 배열로 주어질 때, 해당 다리를 건널 수 있는 최대 인원을 return한다.

문제 풀이

이전에 실패한 문제이다.
구현 문제로 접근하였으나, 최종적으로는 Parametric Search로 풀었다.


이전에는 징검다리의 숫자가 올라가는 경향인지, 내려가는 경향인지 파악하여 문제를 풀었다.
하지만 가장 중요한 것은 로직이 잘못된 것이다.
각 index를 기준으로 k개의 징검다리의 최대값을 구하는데, 각 단계마다 한 개의 다리가 빠지고 한 개의 다리가 추가된다.
이전의 풀이에서 빠지는 다리가 answer과 같을 때 함수 호출을 통해 answer를 갱신하는데, 이 로직이 잘못되었다.
5,1,1,...1,1,6,1,1,...,1,1,5 와 같이 처음과 끝에 5, 중간에 한 개의 6, 나머지는 전부 1인 경우에서 문제가 생긴다.
5가 빠지고 6이 들어오면 해당 k개의 최대값은 6으로, answer는 여전히 5이다.
이 때 6이 빠져도 answer의 갱신 조건과 맞지 않으며, k개보다 많은 1이 나열되어도 검사를 하지 않아 결과는 5가 된다.
결국 모든 k개로 구성된 부분 다리를 확인해야 하며, 이 경우 너무 많은 loop로 인하여 TLE가 발생한다.


최대값은 200M으로, logN의 시간 복잡도라면 30 이내에 해결이 된다.
Parametric Search를 이용하여 값을 구하였다.
0부터 200M의 범위에서 Parametric Search를 시행하며, 최악의 경우 약 30n의 검사를 진행한다.
물론 최악의 경우이므로, 최선의 경우 약 30 * k 를 통해 정답을 구할 수 있었다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;
using std :: max ;
using std :: min ;

bool bCanCrossBridge ( vector < int > & vStone , int iGap , int iLength )
{
    int iCount = 0 ;
    int iStoneSize = vStone.size () ;



    for ( int i = 0 ; i < iStoneSize ; ++i )
    {
        if ( vStone [ i ] < iLength )
        {
            ++ iCount ;

            if ( iCount == iGap )
                return false ;
        }
        else
            iCount = 0 ;
    }


    return true ;
}

int solution ( vector < int > stones , int k )
{
    int iLeft = 0 ;
    int iRight = 2e8 ;
    int iMid ;
    int iAnswer = 2e8 ;


    while ( iLeft <= iRight )
    {
        iMid = ( iLeft + iRight ) >> 1 ;

        if ( bCanCrossBridge ( stones , k , iMid ) )
        {
            iLeft = iMid + 1 ;
            iAnswer = iMid ;
        }
        else
        {
            iRight = iMid - 1 ;
        }
    }


    return iAnswer ;
}