백준 흑백 요리사[32653] 파이썬(Python) 코드 + 해설

백준 32653 흑백 요리사 문제

 

1. 문제 해설

성현이는 각 스테이크의 앞면과 뒷면을 같은 횟수로, 최소 한 번 이상 구워야 한다. 각 면은 한 번 굽는데 해당 스테이크의 두께 x_i​분이 걸린다. 즉, 각 스테이크 iii는 한 면을 구울 때마다 정확히 x_i​분을 사용하고, 총 구워야 할 시간은 2×x_i​×n_i​분이다. 여기서 n_i​는 각 면을 구운 횟수이며, n_i≥1인 정수다.

모든 스테이크는 동시에 불판에 올려지며, 중간에 제거할 수 없다. 또한, 굽는 도중에 스테이크를 뒤집는 시간은 각 스테이크의 두께에 정확히 맞춰야 한다.

목표는 모든 스테이크를 "even"하게 굽기 위한 최소 시간을 찾는 것이다.

2. 문제 해결 방법

2.1 핵심 아이디어

• 각 스테이크의 총 굽는 시간은 𝑇𝑖=2×𝑥𝑖×𝑛𝑖이다.
• 𝑛𝑖 는 각 면을 굽는 횟수로, 최소 1 이상인 정수다.
• 모든 스테이크의 총 굽는 시간이 동일해야 한다. (스테이크를 중간에 제거할 수 없고, 굽는 도중에 불판에서 빼낼 수 없기 때문)
• 따라서, 모든 의 최소공배수(LCM)를 구하면 최소 시간이 된다.

2.2 구현 전략

1. 각 스테이크의 굽는 시간 계산
   • 각 스테이크 iii에 대해, 최소 굽는 시간은 𝑇𝑖=2×𝑥𝑖​이다. 여기서 𝑛𝑖 ​=1인 경우이다.
   • 그러나 𝑛𝑖 ​를 증가시켜  𝑇𝑖 ​를 늘림으로써 전체 시간  𝑇를 줄일 수 있는지 확인해야 한다.
2. 최소공배수(LCM) 계산
   • 모든 𝑇𝑖  ​의 최소공배수를 계산하여  𝑇를 구한다.
   • 𝑥𝑖 ​≤25이므로 𝑇𝑖=2×𝑥𝑖≤50이다.
   • 따라서,  𝑇𝑖 ​는 2부터 50까지의 정수 중 하나다.
3. 소인수분해 및 최대 지수 계산
   • 2부터 50까지의 모든 정수에 대해 소인수분해를 미리 계산한다.
   • 각  𝑇𝑖  ​에 대해 소인수분해를 하고, 소인수의 최대 지수를 기록한다.
   • 모든  𝑇𝑖  ​의 소인수분해 결과에서 소인수의 최대 지수를 사용하여  𝑇를 계산한다.
4. 최종 시간 계산
   • 최종 시간 계산은 다음과 같이 할 수 있다.

3. 백준 32653 흑백 요리사 파이썬(Python) 정답 코드

import sys
import math

# 소수 리스트 (2부터 50까지)
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

# 2부터 50까지의 소인수분해 결과를 저장하는 딕셔너리
factorization = {}

for num in range(2, 51):
    n = num
    factors = {}
    for p in primes:
        count = 0
        while n % p == 0:
            n //= p
            count += 1
        if count > 0:
            factors[p] = count
        if n == 1:
            break
    factorization[num] = factors

# 입력 처리
input = sys.stdin.readline
N = int(input())
xi_list = list(map(int, input().split()))

# 소인수의 최대 지수를 저장할 딕셔너리
max_exponents = {}

for xi in xi_list:
    Ti = xi * 2
    factors = factorization[Ti]
    for p, exp in factors.items():
        if p in max_exponents:
            max_exponents[p] = max(max_exponents[p], exp)
        else:
            max_exponents[p] = exp

# 최소공배수 계산
T = 1
for p, exp in max_exponents.items():
    T *= p ** exp

print(T)

4. 백준 32653 흑백 요리사 파이썬(Python) 코드 해설

 

1. 소인수분해 준비
   • 2부터 50까지의 모든 소수 p를 primes 리스트에 저장한다.
   • 2부터 50까지의 모든 정수에 대해 소인수분해를 수행하고, 결과를 factorization 딕셔너리에 저장한다.
   • 각 숫자에 대해 가능한 소인수 p로 나누어 나머지가 0이 될 때까지 나누고, 해당 소인수의 지수를 기록한다.
2. 입력 처리
   • 표준 입력을 통해 스테이크의 개수 N과 각 스테이크의 두께 𝑥𝑖 ​를 입력받는다.
3. 소인수의 최대 지수 계산
   • 각 스테이크 iii에 대해  𝑇𝑖=2×𝑥𝑖 를 계산한다.
   •  𝑇𝑖 ​의 소인수분해 결과에서 소인수와 지수를 가져온다.
   • 각 소인수 p에 대해 기존에 저장된 최대 지수와 현재 지수를 비교하여 더 큰 값을 max_exponents 딕셔너리에 저장한다.
4. 최소공배수 계산
   • 모든 소인수 p에 대해 최대 지수만큼 거듭제곱하여 곱한다.
   • 이를 통해 모든  𝑇𝑖 ​의 최소공배수  𝑇를 계산한다.
5. 결과 출력
   • 계산된 최소 시간  𝑇를 출력한다.

 

5. 백준 32653 흑백 요리사 제출 결과

백준 32652 파이썬 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다