1952

static int price[4]; //1day, 1month, 3months, 1year 
static int month[12];
 
static int __solution_(int m, int value)
{
    if (m >= 12)
    {
        return value;
    }
    else
    {
        int sel;
        if (month[m] * price[0] < price[1])
            sel = month[m] * price[0];
        else
            sel = price[1];
 
        int r1 = __solution_(m + 1, value + sel);
        int r2 = __solution_(m + 3, value + price[2]);
        return r1 < r2 ? r1 : r2;
    }
}
 
static int __solution(int tot_days, int tot_months)
{
    int min = price[3], v;
     
    v = tot_days * price[0];
    if (v < min)
        min = v;
 
    v = tot_months * price[1];
    if (v < min)
        min = v;
 
    v = 4 * price[2];
    if (v < min)
        min = v;
 
    v = __solution_(0, 0);
    if (v < min)
        min = v;
 
    return min;
}
 
static int solution(void)
{
    int tot_days = 0, tot_months = 0;
 
    for (int i = 0; i < 4; i++)
        scanf("%d", &price[i]);
    for (int i = 0; i < 12; i++)
    {
        scanf("%d", &month[i]);
        tot_days += month[i];
        if (month[i])
            tot_months += 1;
    }
 
    return __solution(tot_days, tot_months);
}

일단 쉽게 생각할 수 있는 부분은 모두 일일이용권을 쓸 때, 모두 한달이용권을 쓸 때, 모두 3달이용권을 쓸 때, 1년이용권을 쓸 때 이다.

그 다음으로 생각해 볼 부분은 이러한 것 들을 조합해서 사용해 볼 때이다.

그래서 모든 경우를 생각해볼 수 있게 재귀로 짜는 것이 좀 더 수월한 것 같다.

 

해당 달에서 일일이용권 만 쓸 때와, 한달 이용권을 쓸 때에 최소 비용은 쉽게 알 수 있기 때문에, 

이 결과를 이용해서 이 중 최소 비용을 썻을 때 얼마가 필요할 지에 대해서 알 수 있고, 그 결과가 r1에 저장된다.

다음은 그냥 3달이용권을 써볼 때 이다. 이 경우에는 해당 달 부터 +2개월 내는 따로 고려할 필요가 없게 된다.

그래서 3달 건너 뛰게 되는 것이고, 그 결과가 r2에 저장되어, 이둘 중 최소값이 반환 되는 것이다.

 

 

 

//cf,

사실 이 문제를 처음 풀 때에는 재귀를 사용하는 것이 아니라 큐를 이용하여 3달 치 가 모였을 때 3달이용권을 쓸 때와 큐에 누적된 비용을 쓸 때 중 최소 비용을 선택하는 방식으로 구현을 해보았다.

샘플 테스트 케이스는 다 맞았지만, 실제 테스트에서는 몇 가지 테스트 케이스를 만족하지 못하는 문제가 있었다.

그 문제점이 정확히 뭔지 몰랐지만 일단 다음에 경우로 생각하였다.

	if (q.size() == 3)
        {
            if (price[2] < acc)
            {
                v += price[2];
                while (!q.empty())
                    q.pop();
                acc = 0;
            }
            else
            {
                v += q.front();
                acc -= q.front();
                q.pop();
            }
        }

3개월 치를 쓰는 것이 낮은 경우에는 큐를 전부 비우고, 그렇지 않으면 큐에 누적된 대로 사용하는 것인데,

여기서 같은 경우를 고려하지 않았다.

 

그래서 3개월 치가 160이고, 현재 큐에 다음과 같이 있다면,

(10 70 80)

여기서 큐를 전부 비우는게 앞으로의 이득일지, 10만 빼는게 앞으로의 이득일지 정확히 알 수 없다는 것이다.

 

그래서 몇가지 경우를 더 생각해보았지만, 크게 상관은 없었기에 아직도 그 차이를 잘 모르겠다.