Programmers - 카운트 다운

---

title: Programmers - 카운트 다운
date: 2022-10-09
tags:

• Algorithm
• DP

---

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

문제 요약

다트의 점수는 1~20과 각 점수는 1배(Single), 2배(Double), 3배(Triple), 50점(Bull)이 존재한다.
점수의 합을 target으로 만들어야 하며, 던진 다트의 수가 제일 적은 것이 best이며, 같은 개수라면 Single + Bull의 값이 가장 큰 것이 좋다.
맞춘 점수의 합을 target으로 만들 때, 가장 적게 던진 다트의 수와 그 때 가장 큰 Single과 Bull의 합을 return한다.

문제 풀이

간단하게 과거의 케이스를 이용하여 현재를 update하는 DP임을 알 수 있다.
다만 20 Triple = 60점으로, Bull보다 점수가 높다.
그렇기에 항상 Bull을 던져 점수를 낮추는 것은 Best가 될 수 없다.
그러므로 target의 값을 확실하게 줄이기 위해서는 수학적 분석을 해야 하며, 귀찮기에 적당한 값을 찾는다.


target 점수를 내리며 0을 만드는 것 = 0부터 점수를 높이며 target을 만드는 것이다. 문제는 후자를 요구하였으며, 이해하기 쉽도록 전자로 적은 것이다.
target - 1부터 1씩 점수를 내리며 이전 점수들을 이용하여 best 경우를 구한다. Bull, 각 점수별 Single, Double, Triple 모두 비교해야 한다.
다만, 일정 값 이상일 때는 20 Triple을 이용해 점수를 낮추는 것이 best라고 가정하였고, 1859까지는 적용할 수 있음을 확인하였다.
전체 DP의 경우 약 10ms 이상 걸리는 케이스가 있는 반면, 해당 값을 적용하면 약 0.5ms 이하의 좋은 성능을 확인할 수 있었다.


수학적으로 분석하면 20 Triple이 best가 되는 일정 값을 찾아낼 수 있을 것 같은데, 정확한 원리는 모르겠다.

프로그램

#include <vector>

using std :: vector ;

bool bCanUpdate ( vector < vector < int > > & vDP , int iCurrentScore , int iScore , int iSingleOrBull )
{
    if ( vDP.size () <= iCurrentScore + iScore )
        return false ;
    if (  vDP [ iCurrentScore ] [ 0 ] < vDP [ iCurrentScore + iScore ] [ 0 ] + 1 )
        return false ;
    if ( ( vDP [ iCurrentScore ] [ 0 ] == vDP [ iCurrentScore + iScore ] [ 0 ] + 1 )
        && ( vDP [ iCurrentScore + iScore ] [ 1 ] + iSingleOrBull <= vDP [ iCurrentScore ] [ 1 ] ) )
        return false ;

    return true ;
}

vector < int > solution ( int target )
{
    int iThrow = 0 ;



    if ( 1800 <= target )
    {
        iThrow = ( target - 1800 ) / 60 ;
        target -= iThrow * 60 ;
    }

    vector < vector < int > > vDP ( target + 1 , vector < int > ( 2 , -1 ) ) ;        // [ iThrow , iSum ]   

    for ( int i = 0 ; i < target ; ++i )
    {
        vDP [ i ] [ 0 ] = target ;
    }
    vDP [ target ] [ 0 ] = iThrow ;
    vDP [ target ] [ 1 ] = 0 ;

    for ( int i = target - 1 ; i >= 0 ; --i )
    {
        if ( bCanUpdate ( vDP , i , 50 , 1 ) )
        {
            vDP [ i ] [ 0 ] = vDP [ i + 50 ] [ 0 ] + 1 ;
            vDP [ i ] [ 1 ] = vDP [ i + 50 ] [ 1 ] + 1 ;
        }

        for ( int iScore = 1 ; iScore <= 20 ; ++iScore )
        {
            for ( int k = 1 ; k <= 3 ; ++k )
            {
                int iSingleOrBull = 1 == k ? 1 : 0 ;

                if ( bCanUpdate ( vDP , i , iScore * k , iSingleOrBull ) )
                {
                    vDP [ i ] [ 0 ] = vDP [ i + iScore * k ] [ 0 ] + 1 ;
                    vDP [ i ] [ 1 ] = vDP [ i + iScore * k ] [ 1 ] + iSingleOrBull ;
                }
            }
        }
    }



    return { vDP [ 0 ] [ 0 ] , vDP [ 0 ] [ 1 ] } ;
}