Programmers - 양궁대회

---

title: Programmers - 양궁대회
date: 2022-07-06
tags:

• Algorithm
• DFS
• BruteForce

---

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

문제 요약

어피치가 어드밴티지를 가지는 양궁 대회이다. 어피치가 먼저 화살을 쐈고, 라이언은 어피치의 화살을 보고 가장 높은 점수차이가 나도록 쏴야 한다.
어떻게 쏘더라도 라이언이 우승할 수 없다면 -1을, 가능하다면 화살을 vector에 넣어 return한다.

문제 풀이

문제를 잘 읽자
문제를 잘못 읽어서 한시간 가까이 삽질하였다.
우선 과녁은 11개이며, 라이언은 어피치가 쏜 화살보다 많이 과녁에 맞춰야 점수를 얻을 수 있다.
라이언의 입장에서 점수를 얻거나, 혹은 아예 쏘지 않고 얻지 않는 두 가지 경우로 구분할 수 있다.
2^11 = 2048으로, 경우의 수가 적기 때문에 완전 탐색을 해도 된다.
점수의 차이가 많이 나는 것이 중요하므로 greedy한 접근은 정답을 찾을 수 없다.

해당 문제는 라이언의 점수가 가장 큰 경우가 아닌, 어피치와의 점수 차이가 가장 큰 경우를 구하는 것이다.
매 상황에서 라이언과 어피치의 점수를 계산하는 것은 오히려 성능 저하가 예상되었고, 이로 인하여 점수는 정답을 구할 때에만 계산한다.

최대 2048가지만 확인하면 되기에 .data 함수가 없더라도 성능 측면에서 문제는 없을 것이다.

프로그램

#include <vector>

using std :: vector ;

int * ipTemp ;
int * ipInfo ;
int * ipAnswer ;
int iMaxGap ;

void Score ()
{
    int iGap = 0 ;

    for ( int i = 0 ; i < 11 ; ++i )
    {
        if ( 0 == ipTemp [ i ] + ipInfo [ i ] )
            continue ;

        iGap += ( ipTemp [ i ] > ipInfo [ i ] ) ? 10 - i : i - 10 ;
    }

    if ( iGap < iMaxGap )
        return ;

    if ( iMaxGap < iGap )
    {
        for ( int i = 0 ; i < 11 ; ++i )
        {
            ipAnswer [ i ] = ipTemp [ i ] ;
        }

        iMaxGap = iGap ;
    }
    else
    {
        for ( int i = 10 ; i >= 0 ; --i )
        {
            if ( ipTemp [ i ] < ipAnswer [ i ] )            // Answer is better, ignore this
                return ;
            else if ( ipTemp [ i ] > ipAnswer [ i ] )        // Current is better, update
                break ;
        }
        for ( int i = 0 ; i < 11 ; ++i )
        {
            ipAnswer [ i ] = ipTemp [ i ] ;
        }
    }
}

void DFS ( int iIndex , int iArrowLeft )
{
    if ( ( 0 == iArrowLeft ) || ( 11 == iIndex ) )
    {
        ipTemp [ 10 ] += iArrowLeft ;
        Score () ;
        ipTemp [ 10 ] = 0 ;

        return ;
    }

    if ( ipInfo [ iIndex ] + 1 <= iArrowLeft )                // Take this score
    {
        ipTemp [ iIndex ] = ipInfo [ iIndex ] + 1 ;

        DFS ( iIndex + 1 , iArrowLeft - ipTemp [ iIndex ] ) ;

        ipTemp [ iIndex ] = 0 ;
        ipTemp [ 10 ] = 0 ;
    }

    DFS ( iIndex + 1 , iArrowLeft ) ;                        // Ignore this score
    ipTemp [ 10 ] = 0 ;
}

vector < int > solution ( int n , vector < int > info )
{
    vector < int > answer ( 11 , 0 ) ;
    vector < int > vTemp ( 11 , 0 ) ;
    int iSum = 0 ;



    ipTemp = vTemp.data () ;
    ipInfo = info.data () ;
    ipAnswer = answer.data () ;
    iMaxGap = 0 ;

    for ( int i = 0 ; i < 11 ; ++i )
    {
        iSum += ( 0 != ipInfo [ i ] ) ? ipInfo [ i ] : 0 ;
    }
    DFS ( 0 , n ) ;

    if ( 0 == iMaxGap )
        return { -1 } ;


    return answer ;
}