โจทย์
มีแท่งโลหะความยาวต่างกัน Container รองรับได้แค่ความยาว 1 ต้องตัดแท่งทั้งหมดให้เป็นหน่วย แล้วใส่ Container (Cost 1 Operation) หา Operations ทั้งหมด
ตัวอย่าง: [6, 3, 7] → Output: 22 (6→10 ops, 3→4 ops, 7→8 ops)
อัลกอริธึม (Prime Factorization + Tree Cost)
- หา Prime Factors ของแต่ละความยาว
- สร้าง Factor Tree คำนวณ Cost การตัด
- Cost = ผลรวมของค่าทุกโหนดใน Factor Tree
โค้ด Python
from math import floor, sqrt
def prime_find(input_num):
prime_check = [True] * ((input_num - 1) // 2)
for p_num in range(3, floor(sqrt(input_num)) + 1, 2):
if prime_check[(p_num - 3) // 2]:
prime_check[(p_num**2 - 3) // 2 :: p_num] = [False] * ((input_num - p_num**2) // (2 * p_num) + 1)
return [2] + [2 * i + 3 for i in range((input_num - 1) // 2) if prime_check[i]]
def solve(input_arr):
prime_nums = prime_find(10**6 + 100)
result = 0
for value in input_arr:
result += value
f_list = []
for p_num in prime_nums:
while value % p_num == 0:
f_list.append(p_num)
value //= p_num
if p_num**2 > value:
if value > 1:
f_list.append(value)
break
temp = 1
for p_num in f_list[::-1]:
result += temp
temp *= p_num
return result
print(solve([6, 3, 7])) # Output: 22
Input / Output
Input: [6, 3, 7]
Output: 22
