[C++] 프로그래머스 - 이모티콘 할인행사

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

프로그래머스

<풀이>

1. 사용자 정보와 이모티콘 정보를 입력받는다.

2. 행사 목적의 최대치를 반환한다.

 

<해법>

1. 알고리즘 선택하기

=> 문제를 읽고 가장 먼저 떠오르는 알고리즘은 모든 경우를 다 해보는 브루트 포스 입니다. 브루트 포스를 사용할 수 있는지 확인하기 위해 시간복잡도를 계산해야합니다. 10, 20, 30, 40%로 7개의 이모티콘 모두 적용해 보아야하고 모든 사용자 100명에 있어서 7개의 이모티콘을 확인해봐야합니다. 시간 복잡도는 O(4^7 x (100 x 7)) = O(11,468,800) 입니다. 따라서, 브루트 포스 알고리즘을 사용할 수 있고 선택했습니다.

 

2. 구현 전 정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 브루트 포스 알고리즘을 사용한다. 7개의 이모티콘에 10, 20, 30, 40% 할인 비율을 모두 적용시키는 것은 재귀함수로 구현한다.

(2) 이모티콘의 가격은 100의 배수로 주어지므로, 가격 연산은 편하게 진행하면 된다.

자세한 구현은 아래 코드를 참고해주세요.

 

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int N, M;
int rate[7];
vector<vector<int>> u;
vector<int> e;
int ansService, ansProfit;
vector<int> answer;
 
int calcPrice(int price, int discountRate) {
    return (price * (100 - discountRate)) / 100;
}
 
void selectDiscountRate(int idx) {
    if (idx == M) {
        int service = 0, profit = 0;
        for (int i = 0; i < N; i++) {
            int price = 0;
            for (int j = 0; j < M; j++) {
                if (rate[j] >= u[i][0]) price += calcPrice(e[j], rate[j]);
            }
            if (price >= u[i][1]) service++;
            else profit += price;
        }
 
        if (service > ansService) {
            ansService = service, ansProfit = profit;
        }
        else if (service == ansService) {
            if (profit > ansProfit) ansProfit = profit;
        }
        return;
    }
    
    for (int i = 10; i <= 40; i += 10) {
        rate[idx] = i;
        selectDiscountRate(idx + 1);
    }
}
 
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    //초기화
    u = users, e = emoticons;
    N = u.size(), M = e.size();
    ansService = 0, ansProfit = 0;
 
    //해법
    selectDiscountRate(0);
    answer.push_back(ansService);
    answer.push_back(ansProfit);
 
    //반환
    return answer;
}

 

브루트 포스에 대해 알아볼 수 있는 문제였습니다.