문제 설명

---

문제

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

입출력

---

문제링크

전체 코드

import heapq
import sys

input = sys.stdin.readline

n, k = map(int, input().split())
arr = []

for _ in range(n):
    m, v = map(int, input().split())
    heapq.heappush(arr,[m,v])

c = []

for _ in range(k):
    heapq.heappush(c, int(input()))

result = 0
capable_gem = []

for i in range(k):
    top = heapq.heappop(c)

    while arr and top >= arr[0][0]:
        [m, v] = heapq.heappop(arr)
        heapq.heappush(capable_gem, -v)
    
    if capable_gem:
        result -= heapq.heappop(capable_gem)
    elif not arr:
        break

print(result)

---

해결 방법

내가 풀지 못했다ㅠㅠ. 다른 사람의 코드를 참조했다.

---

1. [ SET x 8 ] 인 리스트를 만듭니다. 각각 N을 1개로 표현하는 수들의 집합, 2개로 표현하는 수들의 집합, ... 8개로 표현하는 수들의 집합이 저장됩니다.
2. 8개의 SET에 개수만큼 N을 연달아 표현되는 수를 집어넣어줍니다.
3. 숫자 N에 대해서 n개를 사용해서 표현한 수의 일반화 수식을 코드로 표현합니다.

• i에 대해서 1-8까지 순회합니다.
• j에 대해서 0-i까지 순회합니다.
• j개를 사용해서 만든 수들의 집합 s[j]를 다음과 같이 순회합니다.
• i-j-1을 사용해서 만든 수들의 집합 s[i-j-1]를 다음과 같이 순회합니다.
• op1(s[j] 순회 수)과 op2(s[i-j-1] 순회 수)를 사칙연산합니다. 나눗셈 시 op2는 0이 되면 안됩니다.
• 사칙연산한 결과 값을 집합 s[i]에 추가합니다.

4. 만약 number가 s[i]에 존재한다면, 반복을 멈추고 i+1번을 반환합니다.
5. 8번을 순회했음에도, number를 못찾는다면, -1을 반환합니다.

---

• 출처 : https://gurumee92.tistory.com/164