문제 개요
서로 다른 길이를 가진 여러 개의 금속 막대를 운송해야 하는 상황을 가정해 봅시다. 그런데 운송용 컨테이너의 길이가 짧아서 길이가 1인 막대만 담을 수 있습니다. n개의 막대가 주어지고, 각 막대의 길이는 리스트 형태로 제공됩니다. 모든 막대를 컨테이너에 넣으려면 먼저 모든 막대를 잘라 단위 길이(1)로 만들어야 하며, 이후 잘라 놓은 막대들을 컨테이너에 포장하는 데 한 번의 작업(operation)이 소요됩니다. 우리가 구해야 할 것은 바로 이 과정에서 필요한 총 작업 횟수입니다.
예시로 이해하기
입력이 input_arr = [6, 3, 7]이라면 출력은 22가 됩니다.
길이 6짜리 막대를 길이 1짜리 막대들로 만들려면 10번의 작업이 필요합니다.
길이 3짜리 막대를 길이 1짜리 막대들로 만들려면 4번의 작업이 필요합니다.
길이 7짜리 막대를 길이 1짜리 막대들로 만들려면 8번의 작업이 필요합니다.
즉, 10 + 4 + 8을 모두 더한 22가 최종 정답이 됩니다.
풀이 접근 방법
이 문제는 에라토스테네스의 체(Sieve of Eratosthenes)로 소수를 미리 구해 둔 뒤, 각 막대의 길이를 소인수분해하고 그 결과를 활용해 작업 횟수를 누적하는 방식으로 해결할 수 있습니다. 해결 절차는 다음과 같습니다.
prime_find()함수를 정의합니다. 이 함수는input_num을 입력으로 받습니다.prime_check := ((input_num − 1)/2)의 내림값 크기를 가지며, 값이 모두 True인 새 리스트를 생성합니다.
p_num을 3부터 √input_num의 내림값 + 1까지 2씩 증가시키며 반복합니다.
prime_check[(p_num − 3)//2]가 참(0이 아님)이라면,
(p_num² − 3)/2의 내림값 인덱스부터 p_num 간격으로 prime_check의 각 요소를 다음과 같이 갱신합니다.
prime_check[element] := ((input_num − p_num²)/(2 × p_num) + 1)의 내림값 개수만큼 False로 채운 리스트
i를 0부터 (input_num − 1)/2의 내림값까지 반복합니다.
prime_check[i]가 True이면 −
소수 2와 함께 (2 × i + 3) 값들로 이루어진 리스트를 반환합니다.
메인 함수에서는 다음을 수행합니다 −
prime_nums := prime_find(10⁶ + 100)
result := 0
input_arr의 각 값(value)에 대해 다음을 수행합니다.
result := result + value
f_list := 새 빈 리스트
prime_nums의 각 소수 p_num에 대해 다음을 수행합니다.
value가 p_num으로 나누어떨어지는 동안 반복합니다.
f_list의 끝에 p_num을 추가합니다.
value := value ÷ p_num의 몫(내림값)
p_num² > value이면,
value > 1이면 f_list의 끝에 value를 추가합니다.
반복문을 종료합니다.
temp := 1
f_list를 역순으로 순회하며 각 p_num에 대해 다음을 수행합니다.
result := result + temp
temp := temp × p_num
result를 반환합니다.
파이썬 구현 예제
아래 구현 예제를 살펴보면 더 잘 이해할 수 있습니다 −
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::-1]:
result += temp
temp *= p_num
return result
if __name__ == "__main__":
print(solve([6, 3, 7]))
입력
[6, 3, 7]
출력
22
코드 동작 원리 정리
prime_find()는 에라토스테네스의 체를 변형한 방식으로 10⁶ + 100까지의 모든 소수를 미리 계산해 둡니다. solve() 함수는 우선 모든 막대 길이의 합을 결과에 더한 후, 각 막대의 길이를 작은 소수부터 차례로 나누어 소인수분해합니다. 이때 어떤 소수의 제곱이 남은 값보다 커지면 더 이상 나눌 필요가 없으므로 반복을 멈추고, 1보다 큰 값이 남아 있다면 그 값 자체가 소수이므로 인수 목록에 추가합니다. 마지막으로 소수 목록을 역순으로 순회하면서 누적 곱(temp)을 결과에 더해 주면, 전체 막대를 처리하는 데 필요한 총 작업 횟수를 구할 수 있습니다.