[C++] 백준 1661번 : 다솜이의 신발 가게

🔗 문제

https://www.acmicpc.net/problem/1661

 

 

 

✏️ 풀이

발상이 떠오르지 않아서 고생했는데 다 풀고 나니 조금 허무하다.

푼 사람이 별로 없는 문제라 나처럼 고민하는 사람들을 위해 리뷰를 쓴다.✌🏻

 

부분집합으로 도전하면 시간 초과. 문제 조건을 고려하면 최악의 경우 O(2^50)가 된다.

시간을 2초나 주기 때문에 혹시 몰라 나름 가지치기도 하고 제출했지만 시간 초과였다.

 

정답의 접근방법은 같은 할인율이라면 싼 신발을 구매하는 그리디 발상이 필요하다.

그래서 같은 할인율대로 신발 저장한 후, 오름차순 정렬을 해준다. 
그 후 할인율 1, 2, 3 % 에서 각각 i, j, k개를 골랐을 때를 모두 조합해보면 된다. 

    int per, price;
    for(int i=0; i<N; ++i)
    {
        cin >> price >> per;
        info[per].push_back(price);
    }

    for(int i=1; i<=3; ++i)
        sort(info[i].begin(), info[i].end());

 

 

WHY?

만약 할인률이 3%인 신발이 3개가 있고 가격이 {1, 2, 3}라고 해보자. 

이 중 2개를 구매한다고 1, 2 신발을 사는게 유리하다.

2개를 고를 때 굳이 1, 3이나 2, 3을 샀을 때를 고려할 필요가 없다. 

 

 

 

 

🧠 개선점

누적합을 하면 중복되는 계산을 제거할 수 있다. 

그렇지만 좀 더 많은 메모리를 사용하는 점과 이 문제에서 시간이 비교적 넉넉한 2초를 줘서 3중 포문을 돌렸다. 

 

 

💾  소스

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
vector<pii> arr;

int N, P;

vector<vector<int> > info(4);
double solve(const int a, const int b, const int c)
{
    double result = 0;
    double per = P;

    for(int i=0; i<a; ++i) {
        per = per * 0.99f;
        result += info[1][i];
    }
    for(int i=0; i<b; ++i) {
        per = per * 0.98f;
        result += info[2][i];
    }
    for(int i=0; i<c; ++i) {
        per = per * 0.97f;
        result += info[3][i];
    }

    return result + per;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> P;

    int per, price;
    for(int i=0; i<N; ++i)
    {
        cin >> price >> per;
        info[per].push_back(price);
    }

    for(int i=1; i<=3; ++i)
        sort(info[i].begin(), info[i].end());

    double answer = 1e9;
    for(int i=0; i<=info[1].size(); ++i)
        for(int j=0; j<=info[2].size(); ++j)
            for(int k=0; k<=info[3].size(); ++k)
                answer = std::min(answer, solve(i, j, k));

    printf("%lf", answer);
    return 0;
}