[백준/16936/파이썬] 나3곱2

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

16936번: 나3곱2

Problem

• 나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를 구해보자.

SOL

보자마자, 아 이건 재귀적으로 구현해야겠구나라는 느낌이 들었다. 

(사실, 재귀를 잘 쓰지 못하는 필자이지만, 위와 같은 문제를보면 똑같은 논리를 가지고 같은 배열을 계속 탐사하는데는 재귀가 최고다)

 

재귀를 짤 때, 난 아래 3가지를 생각하면서 짠다. (어려운 과정이다)

• 출발점을 정해야한다.
  • 이 문제에서는, 모든 경우를 봐야하기 때문에, 그냥 편의상 첫번째 원소부터 차례대로 보기로 했다.
• 탈출점을 설정해야한다.
  • return True인 경우 (A 배열이 이루어지는 경우) => B 배열이 전부 비워졌을 때, True로 탈출
  • isPossible이 끝까지 False일 때 -> False로 탈출
• 3. 재귀를 시작하는 조건을 설정해야한다.
  • x*2,x%3==0,x//3이 b안에 있을 때, 재귀를 돌아준다. (다음 원소를 골라준다)

import sys
input =sys.stdin.readline
N=int(input().rstrip())
B=list(map(int,input().split()))
#시작점은, B[i]의 원소 
def solve(x,b,ans):
	b.remove(x)
    ans.append(x)
    isPossible=False
    if not b:
    	return True
    if x*2 in b:
    	isPossible=True
    	return solve(2*x,b,ans)
    if x%3==0 and x//3 in b:
    	isPossible=True
    	return solve(x//3,b,ans)
    if not isPossible:
    	return False
    
for i in range(N):
	ans=[]
    res=solve(B[i],B.copy(),ans)
    if res:
    	print(*ans)
        break