백준 1661 - 다솜이의 신발가게

작성일 | In

백준 풀이 업로드 기준 : 다음 중 하나 이상 만족

  1. 내가 첫 solve
  2. 내가 첫 contributor
  3. 내가 의미있다고 생각하는 문제
  4. 구글링해도 풀이가 나오지 않는 문제

문제

문제 링크

[다솜이의 신발가게]

문제

다솜이는 최첨단 유행을 달리는 신발가게를 운영하고 있다. 하지만 다솜이의 가게에는 유행에 덜떨어진 이상한 제품들도 있다. 다솜이는 유행에 덜떨어져서 사람들이 사가지 않는 제품을 더 사기 위해서, 새로운 할인 시스템을 구축했다.

할인 시스템은 다음과 같다.

유행에 덜 떨어진 제품을 C원을 주고 사면, 유행을 달리는 제품을 P% 할인 받아서 살 수 있다. 하지만, 다솜이는 욕심이 많기 때문에, P는 1,2,3 중에 하나이다.

하지만 이러한 할인 시스템이 잘 작동하지 않았다. 다솜이는 유행에 덜 떨어진 물건을 N개 사면, 누적해서 할인을 받을 수 있게 해주었다. 예를 들어, 유행에 떨어진 제품 중에 2%할인 받는 제품과 3%할인 받는 제품을 샀다면, 유행을 달리는 제품 100 짜리를 100*0.98*0.97 = 95.06에 살 수 있다.

입력으로 현재 다솜이의 신발가게에서 할인을 해주는 유행에서 떨어진 제품의 가격과 그 것을 샀을 때 유행을 달리는 제품을 얼마나 할인해주는지 주어졌을 때, 영식이가 사고 싶어 하는 제품 P를 얼마나 작은 가격으로 살 수 있는 지 그 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 유행에 떨어진 제품의 개수 N과 영식이가 사고 싶어 하는 제품 P의 가격이 들어온다. N은 50보다 작거나 같은 자연수이다. P는 1,000,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각각의 유행에 덜떨어진 제품의 가격 C와 그 물건을 샀을 때 할인 받을 수 있는 할인율 P가 주어진다. C는 10,000,000보다 작거나 같은 자연수이고, P는 1, 2, 3 중에 하나다.

출력

첫째 줄에 영식이가 사고싶어하는 신발 P를 얼마나 낮은 가격으로 살 수 잇는지 출력하시오. 절대/상대 오차는 10^-6^까지 허용한다.

풀이

전략

전제와 제약을 최대한 많이 찾아내야 풀이 찾기가 편하다. 문제를 잘 분석해 보면 다음과 같은 제약을 추려낼 수 있다.

  1. 유행에 덜 떨어진 제품을 구매하는 순서는 상관없다. 어느 조합으로 구매하느냐가 중요하다.
    1. 앞으로는 조합을 이용해 설명한다.
  2. 다만 모든 조합은 직접 탐색해보기 전에는 그 조합이 최저가격인지 알 수가 없다.
    1. 현재 상태에서 최적의 선택을 알기는 불가능하다. 따라서 조합의 탐색은 불가피하다. -> DFS
  3. 동일한 할인율을 가진 ‘유행에 덜떨어진 제품’ 중에서 가장 저렴한 것을 선택하는 것이 ‘무조건 좋다’
    1. 1번 제약으로부터 파생되는 개념이다.
    2. 조합에 원소를 좋은 것 부터 포함시켜 나갈 때, 어느 순간에 끊을 것인지 선택해야 하는데 그 기준은 ‘이득인가 손해인가’ 이고, 손해가 시작되는 시점부터는 조합에 포함시킬 이유가 없다. (포함해서는 안된다)

문제 오답자들의 코드를 보면 대부분 2번 제약사항까지 고려해서 DFS로 풀었다가 시간 초과로 틀리고, 3번 제약사항을 떠올려낸 사람들은 솔브를 띄웠다.

‘유행에 덜 떨어진 제품’을 입력으로 받은 뒤 다음과 같은 자료 구조로 가공하고, DFS로 탐색 시 시간 내에 답을 찾을 수 있다.

1
2
3
['유행을 달리는 제품에' 1%의 할인이 적용되는 '유행에 덜떨어진 제품'의 가격 오름차순 목록,
'유행을 달리는 제품에' 2%의 할인이 적용되는 '유행에 덜떨어진 제품'의 가격 오름차순 목록,
'유행을 달리는 제품에' 3%의 할인이 적용되는 '유행에 덜떨어진 제품'의 가격 오름차순 목록]

코드

1
2
3
4
5
6
7
8
9
N, P = map(int, input().split())
DC = [[], [], []]

for i in range(N):
    c, p = map(int, input().split())
    DC[p-1].append(c)

for i in range(3):
    DC[i].sort()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ancient = [[[False for i in range(51)] for j in range(51)] for k in range(51)]

min_cost = 1000000000
def DFS(p1, p2, p3, unt_cost, P):
    if ancient[p1][p2][p3]:
        return
    else:
        ancient[p1][p2][p3] = True

    global min_cost
    cost = unt_cost + P
    if min_cost > cost:
        min_cost = cost

    if p1 < len(DC[0]):
        DFS(p1+1, p2, p3, unt_cost+DC[0][p1], P*0.99)
    if p2 < len(DC[1]):
        DFS(p1, p2+1, p3, unt_cost+DC[1][p2], P*0.98)
    if p3 < len(DC[2]):
        DFS(p1, p2, p3+1, unt_cost+DC[2][p3], P*0.97)

DFS(0, 0, 0, 0, P)
print(min_cost)

ancient는 아마 없어도 잘 돌아갈 거라 생각하는데, 그냥 중복 탐색이 싫어서 시간 최적화 겸 넣었다..