[BOJ] - 16936

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

완전탐색

• 가능한 모든 경우의 수를 탐색하는 유형이다

• 재귀 형태로 문제를 푸는경우가 많으며, 각 단계마다 가능한 경우는 다음 재귀를 실행시키고 불가능한경우는 넘어간다

• 재귀의 끝 (탈출조건)에 도달했을 때, 1을 리턴해 경우의 수를 카운트한다

• 경우의 수를 세는 문제는 완전탐색 유형이다

• 브루트 포스는 완전 탐색 알고리즘이다

  • 선형구조는 순차 탐색
    비선형구조는 DFS 또는 BFS 를 이용한다

• 즉, for 문 돌면서 하나씩 조건 체크하는 방식으로 문제를 풀거나

• DFS, BFS 등을 사용해가며 문제를 푼다

노트

1) permutation 돌리는 방법

from itertools import permutations

seq = [1,2,3,4]
permute = permutations(seq, 3) # seq 에서 3개 뽑는 순열

print(list(permute))

---

from itertools import combinations

seq = [1,2,3,4]
combi = combinations(seq, 2)  # seq 에서 3개 뽑는 조합

print(list(combi))

풀이

가능한 경우가 나올 때까지 모든 경우의 수를 테스트한다

단, permutation으로 순열을 만들어 테스트하는게 아니라,

순열의 시작 숫자를 정하고,
2의 배수 또는 3으로 나눠지는 수가 있는지 찾아가면서 순열을 만들어나가고,

더이상 만들 수 없으면 False 리턴,
만들기가 끝났으면 True를 리턴한다

문제점

모든 순열을 생성해 테스트하면 정답은 찾을 수 있지만, 시간초과가 나온다

다른 방법을 생각했어야 했다

코드

import sys
from itertools import permutations


def solve(x, b, A):
    b.remove(x)
    A.append(x)
	
    # 최종단계에서 순열을 무사히 완성했으면 True를 리턴한다
    if not b:
        return True

    least_one = False
    if x*2 in b:
        least_one = True
        # 다음 순열 완성가능한지 테스트
        return solve(x*2, b, A)
    if x % 3 == 0 and x//3 in b:
        least_one = True
        # 다음 순열 완성가능한지 테스트
        return solve(x//3, b, A)

	# 탐색 도중, 더이상 탐색할 수 없고, 순열을 완성하지 못했으므로 False 리턴
    return least_one


sys.stdin = open('16936.txt')

n = int(input())
seq = list(map(int, input().split()))

for i in range(n):
    x = seq[i]
    A = []
    flag = solve(x, seq.copy(), A)
    if flag:
        print(*A)
        break