[프로그래머스/python] Level 2 : 이모티콘 할인 행사

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

프로그래머스

문제 독해 능력이 중요한 구현 문제이다 ㅋㅋ

 

읽어보면 알겠지만, 모든 가능한 할인율의 경우의 수를 전부 대입하여 풀어봐야한다. 즉 브루트 포스 + 백트래킹 구현 문제 정도로 생각할 수 있다.

 

문제 풀이는 다음과 같다.

1. 필요한 변수들을 선언해주고 dfs를 시작한다

2. 할인율의 경우의 수를 기록하는 배열을 sale_board라 할 때, 이 배열이 다 채워지면 cal() 함수를 호출해서 각 경우의 최대 이모플 가입자와 구매 가격을 계산한다

3. 계산된 값을 answer와 비교하여 더 큰 값을 넣어준다. 이 때 [이모플 가입자 수, 이모티콘 구입 금액]은 한 세트라는 걸 놓치지 말자!

 

tmi. 유저의 구매 기준과 할인율을 비교하는 if문에서 뭐에 홀렸었는지 부등호를 반대로 적었다ㅜ

이런 실수는 아무리 간단한 문제라도 쉽게 저지를 수 있고, 쉽게 찾지 못한다는 것이 큰 문제이다. 주의하자,,,

answer = [0,0]
def solution(users, emoticons):
    n = len(users)
    m = len(emoticons)
    sale_percent = [40,30,20,10]
    sale_board = [0] * m
    def dfs(idx):
        global answer
        
        def cal():
            cnt = 0; sale_money=0;
            for i in range(n): # 유저 별로
                money = 0
                for j in range(m): # 이모티콘 별
                    if users[i][0] <= sale_board[j]: # 만약 유저의 구매 기준이 할인율 보다 높다면
                        money += emoticons[j] * ((100-sale_board[j])/100) # 구매
                        if money >= users[i][1]: # 만약 구매 시, 비용을 초과한다면
                            cnt += 1 # 이모플 가입자 +1
                            money = 0
                            break
                sale_money += money

            return [cnt, sale_money]
        
        if idx == m:
            tmp = cal()
            if tmp[0] > answer[0] : answer = tmp
            elif tmp[0] == answer[0]:
                if tmp[1] > answer[1]:
                    answer = tmp   
            return

        for i in range(4):
            sale_board[idx] = sale_percent[i]
            dfs(idx+1)
    
    dfs(0)

    return answer