[BOJ / 백준] 16936번 나3곱2 파이썬(Python) 문제 풀이

 

문제

 

문제 링크 : https://www.acmicpc.net/problem/16936

16936번: 나3곱2

 

 

 

 

 

CODE

n = int(input())
num = [int(x) for x in input().split()]
result = []

first_value = num[0]
max_pow = 0

# 첫번째 값 찾기
for i in range(n):
    temp = num[i]
    pow = 0
    while temp % 3 == 0:
        temp //= 3
        pow += 1
    if (pow > max_pow) or (pow == max_pow and num[i] < first_value):
        max_pow = pow
        first_value = num[i]

result.append(first_value)

# 다음 순서인 수 찾기
for i in range(n):
    if result[-1] * 2 in num:
        result.append(result[-1] * 2)
        continue
    if result[-1] % 3 == 0 and result[-1] // 3 in num:
        result.append(result[-1] // 3)
        continue
    break

if len(result) == n:
    print(*result)

 

 

 

 

 

풀이

- 나3곱2로 정렬된 수열은 오른쪽으로 갈수록 2^n배, 3^-n배 증가한다

- 3의 n승을 약수로 갖는 수들은 오른쪽으로 갈수록 3의 차수가 감소한다

- 같은 n의 3의 n승을 약수로 갖는 수들은 오른쪽으로 갈수록 수가 크다

따라서 정답 수열의 첫 번째 수는 가장 큰 3의 n승을 약수로 갖는 수들 중 가장 작은 수이다

첫 번째 수를 구하고 나면 나3곱2의 법칙에 따라 다음 수들을 구할 수 있다

 

 

 

 

 

결과