[백준][C++] 11508 2+1 세일

11508. 2+1 세일

11508번: 2+1 세일

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

앞 문제와 같이, 정렬과 가까운 문제였다.

 

알고리즘 설계

1. 가격들이 모두 있는 배열을 내림차순으로 정렬한다.

 (9 8 7) (6 5 4) 3 2

2. 인덱스대로 3개씩 묵어 첫번째와 두번째 값만 더해준다.

 (9 8 7) (6 5 4) 3 2
 result = 9 + 8 + 6 + 5

3. 3개로 묶어지지 않은 나머지들을 전부 더해준다.

 (9 8 7) (6 5 4) 3 2
 result += 3 + 2

 

배열을 내림차순으로 정렬한 이유는, 3개로 묶었을 때 가장 저렴한 유제품의 가격이 할인되므로, 되도록 가격이 나가는 유제품을 할인받는 것이 최소 가격으로 구매하는데 적절하다.

 

더 원활한 이해를 위해 테스트 케이스를 그려봤다.

 

아무튼... 알고리즘으로 코드를 짰는데...

int main()
{
    vector<int> prices;
    int len, i;
    long long int myCost = 0;

    cin >> len;
    prices.resize(100000);

    for (i = 0; i < len; i++)
        cin >> prices[i];

    sort(prices.begin(), prices.end(), greater<int>());

    // 현재 인덱스: 0부터 시작함
    i = 0;

    if (len / 3 > 0)
    {
        for (i = 0; i < len; i += 3)
        {
            // 세 개로 묶인 것들 중에 첫번째, 두번째만 더함
            myCost += (long long int)prices[i] + prices[i + 1];
        }
    }

    // 묶이지 않은 가격들을 더함
    while (i < prices.size())
    {
        myCost += prices[i++];
    }

    cout << myCost;
}

이렇게 짜니... index를 나타내는 i가 자꾸 눈에 걸려서 깔끔하지가 않은 것 같아서 아쉬웠다.

 

그래서 비용을 더하는 방식을 바꿨다.

1. 가격들이 모두 있는 배열을 내림차순으로 정렬하고, 모두 더한 값을 result에 넣어준다..

 (9 8 7) (6 5 4) 3 2
 result = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2

1. 인덱스대로 3개씩 묵어 세번째 값만 빼준다..

 (9 8 7) (6 5 4) 3 2
 result -= (7 + 4)

 

이것을 코드로 짜봤다.

int main()
{
    //...

    // 모든 가격을 더해준다.
    for (int i = 0; i < len; i++)
    {
        cin >> prices[i];
        myCost += prices[i];
    }

    sort(prices.begin(), prices.end(), greater<int>());

    if (len / 3 > 0)
    {
        // 세 개로 묶어 세번째 것만 빼준다.
        for (int i = 2; i < len; i += 3)
        {
            myCost -= prices[i];
        }
    }

    cout << myCost;
}

코드도 짧아지고 훨씬 깔끔해진 것 같아 마음에 든다!!!