[백준] 1661 - 다솜이의 신발가게 (Python)

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

 

문제 분류를 봐도 아이디어를 떠올리기 힘들었던 문제

분류를 보기 전까지는 자연스럽게 그리디가 계속 떠올랐다.

 

우선 N이 작기때문에 뭔가 다 해보면 될 것 같다는 생각은 든다.

그런데 어떻게 다 해봐야할 지 감이 잘 안온다.

이 문제를 풀 때는 한번 예제 입력 1번에 해당하는 케이스를 다 써보면 풀이를 떠올릴 수 있다.

 

예제 입력에 1번에 있는 물건 3개에 대해서 각각을 사는지 안사는지 경우의 수를 모두 따지면 이렇게 8가지가 나온다.

이를 직접 손으로 다 쓰다보면 규칙이 보인다.

 

어쨌든 할인율은 결국 1, 2, 3 프로중 하나밖에 없다.

그리고 최종 할인되는 가격은 어떤 물건을 먼저 사느냐에 상관없이 항상 기존 가격 * 각각의 할인율들의 곱으로 표현된다.

 

이를 식으로 나타내면 위 이미지의 하단과 같은 수식을 뽑을 수 있다.

 

이제 이 문제는 위 수식에서 x, y, z 로 가능한 모든 조합을 시도해보는 문제가 되었다!

이때 유행에 덜떨어진 물건을 구매하는 추가금은 최대한 덜 내는 것이 좋으므로, 각각의 x, y , z 조합에서 내야하는 추가금이 최소가 되도록 미리 사전에 각 조합별 최소 추가금을 구해둔다.

 

나는 누적합 배열을 이용해서 구해뒀다.

 

n, price = map(int, input().split())
one = []
two = []
three = []
for _ in range(n):
    product_price, sales_rate = map(int, input().split())
    if sales_rate == 1:
        one.append(product_price)
    elif sales_rate == 2:
        two.append(product_price)
    elif sales_rate == 3:
        three.append(product_price)

one.sort()
two.sort()
three.sort()

# 누적합 구해놓기
acc_one = [0]
for i in range(len(one)):
    acc_one.append(acc_one[-1] + one[i])

acc_two = [0]
for i in range(len(two)):
    acc_two.append(acc_two[-1] + two[i])

acc_three = [0]
for i in range(len(three)):
    acc_three.append(acc_three[-1] + three[i])

answer = price
for i in range(n+1):
    if i > len(one):
        break
    for j in range(n+1):
        if j > len(two):
            break
        if i + j > n:
            break
        for k in range(n+1):
            if k > len(three):
                break
            if i + j + k > n:
                break

            check = price * (0.99**i) * (0.98**j) * (0.97**k) + acc_one[i] + acc_two[j] + acc_three[k]

            answer = min(answer, check)

print(answer)

 

최종 정답코드는 위와 같다.

1, 2, 3 퍼센트 할인율에 대해 따로따로 변수 이름을 지어두느라 코드가 길어졌는데, 리스트나 딕셔너리로 관리했으면 더 간단하게 작성할 수도 있을 것 같다.

 

n, price = map(int, input().split())
sales = [[], [], [], []]
for _ in range(n):
    product_price, sales_rate = map(int, input().split())
    sales[sales_rate].append(product_price)

for i in range(1, 4):
    sales[i].sort()

# 누적합 구해놓기
acc = [[], [0], [0], [0]]
for sales_rate in range(1, 4):
    for i in range(len(sales[sales_rate])):
        acc[sales_rate].append(acc[sales_rate][-1] + sales[sales_rate][i])

answer = price
for i in range(len(sales[1])+1):
    for j in range(len(sales[2])+1):
        if i + j > n:
            break
        for k in range(len(sales[3])+1):
            if i + j + k > n:
                break

            check = price * (0.99**i) * (0.98**j) * (0.97**k) + acc[1][i] + acc[2][j] + acc[3][k]
            answer = min(answer, check)

print(answer)

 

깔끔하게 리펙토링한 코드이다.