백준 16936 나3곱2 파이썬(python)

 

문제

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

나3곱2 게임을 진행하면서, 만든 수를 모두 기록하면 수열 A를 만들 수 있다. 예를 들어, x = 9, N = 6이고, 적용한 연산이 곱2, 곱2, 나3, 곱2, 나3인 경우에 A = [9, 18, 36, 12, 24, 8] 이다.

수열 A의 순서를 섞은 수열 B가 주어졌을 때, 수열 A를 구해보자.

입력

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 수열 B가 주어진다. B에 포함된 원소는 1018 보다 작거나 같은 자연수이다.

출력

나3곱2 게임의 결과 수열 A를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

---

풀이

[알고리즘]

수열의 크기가 N이 100까지 가능하니 완탐은 피해야 했고 괜찮은 방법이 없을까 하다가 곱2, 나3 연산 방식의 결과는 유일하다는 것을 알게 됐고 연산 결과 값이 본래 리스트에 존재한다면 Hash k-v로 묶고 나중에 이어주는 형식으로 풀어주었다.

나3곱2 간단 풀이

[풀이 방법]

1. 연산 결과 값 체크 시간을 줄이기 위해 set() 이용
2. 값이 있다면 dictionary 이용해 k-v 묶음.
3. 연산 결과 값이 없는건 check 변수 통해 판별.
4. 결과 값 reverse 피하기 위해 deque() 사용해 앞에서부터 추가.
5. value 값이 0이면 break (key error 피하기 위해 defaultdict 사용)

from collections import defaultdict, deque

N = int(sys.stdin.readline())
nums = set(map(int, sys.stdin.readline().split()))
store = defaultdict(int)
start = 0
for num in nums:
    check = 0
    if not num % 3 and num // 3 in nums:
        check += 1
        store[num // 3] = num
    if num * 2 in nums:
        check += 1
        store[num * 2] = num
    if not check:
        start = num
answer = deque()
while True:
    answer.appendleft(start)
    if not store[start]:
        break
    start = store[start]
print(*answer)

---

출처 : https://www.acmicpc.net/problem/16936

16936번: 나3곱2