🔴 문제 개요
🚀 난이도 : GOLD 5
나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 보다 작거나 같은 자연수이다.
🟠 Solution
기존 수열에서 순서가 섞였기 때문에 본 수열을 복원하기 위해서 단순히 모든 경우의 수를 고려해볼 수 있습니다. 하지만 N이 100까지 주어질 수 있으므로, 이 경우 최대 100! * (나3곱2 조건을 만족하는지 판별) 하는 만큼의 어마무시한 연산이 수행되게 되겠죠.
그렇기 때문에, 모든 경우의 수를 고려하되, 중간의 결과가 조건을 만족하지 않으면 더 이상 해당 경우에서 다른 경우로 상태가 전이되는 것을 막으며 진행하는 백트래킹을 활용할 수 있습니다.
위와 같이 수를 하나씩 포함해나가며 조건에 맞는 경우에만 다른 경우로 계속 상태를 전이하는 방법입니다. 기본적으로 재귀를 활용한 DFS를 적용할 수 있겠죠. 코드를 보겠습니다.
먼저 입력부와 함수의 인터페이스, 메인부입니다.
import sys
from typing import List
input = sys.stdin.readline
N = int(input().rstrip())
nums = list(map(int, input().rstrip().split()))
visited = [False for _ in range(N)]
result = None
def dfs(tmp: List[int]) -> None:
"""
nums의 수를 하나씩 포함해보는 백트래킹을 수행하여 global 변수 result에 최종 수열을 주입한다.
"""
pass
for idx in range(N):
visited[idx] = True
dfs([nums[idx]])
visited[idx] = False
print(*result)
방문처리를 위한 visited 배열을 선언했습니다. 이미 넣은 수는 수열에 포함하면 안되겠죠. dfs는 새로 구성할 수를 하나씩 수열에 포함하는 방법으로 재귀를 진행합니다. 수열의 상태는 매개변수로 다음 상태로 전이됩니다.
프로그램의 하단 메인부를 보면 초기 상태에서 nums안의 수를 하나씩 포함하여 재귀를 시작합니다. 이때 재귀 시작 전 해당 수에 대한 방문 처리를 해주고, 재귀 탈출 후 방문 처리를 해제해줘야 다음 반복 때 해당 수를 고려하며 재귀를 수행할 수 있게 되겠죠. 백트래킹의 기본 구조입니다.
이제 dfs 함수를 정의해보겠습니다.
def dfs(tmp: List[int]) -> None:
"""
nums의 수를 하나씩 포함해보는 백트래킹을 수행하여 global 변수 result에 최종 수열을 주입한다.
"""
global result
if len(tmp) == N: # N개의 수가 채워졌으면 result에 값을 주입하고 함수 종료
result = tmp
return
for idx in range(N):
if not visited[idx] and (
# 나3곱2 규칙 적용
(tmp[-1] % 3 == 0 and tmp[-1] // 3 == nums[idx])
or tmp[-1] * 2 == nums[idx]
):
# 백트래킹
visited[idx] = True
dfs(tmp + [nums[idx]])
visited[idx] = False저는 재귀를 활용한 dfs시 반환 값을 받는 부분에 대해서 헷갈리는 부분이 있어서 늘 global 변수에 값을 주입하는 방법으로 코드를 구성하곤 합니다.
기본적으로 재귀 메서드에는 재귀를 탈출하기 위한 조건이 있어야 합니다. 이 문제에서는 수열 A가 존재하는 것이 보장되어있기 때문에 중간 수열의 크기가 N이 되면 결과 변수에 값을 주입하고 재귀를 탈출할 수 있도록 합니다.
다음은 이 문제의 핵심입니다. 현재 상태에서 포함을 시도해보지 않은 수들에 대해서 수열에 추가하려는 시도를 해봅니다. 즉, 나3곱2 규칙을 적용했을 때 포함할 수 있는 경우에 대해서만 다음 상태로 재귀를 진행하는 것입니다. 나3곱2 규칙을 idx번째 수가 만족한다면, 현재 수열에 상태에 nums[idx]를 포함시켜 다음 상태로 재귀합니다. 재귀 전 후로 해당 수를 포함했다는 방문처리를 해줘야겠죠.
나3곱2 규칙의 나눗셈에 대한 부분에서 '3으로 나누어 떨어져야 한다'라는 규칙이 있습니다. 따라서 tmp[-1] % 3 == 0 조건을 추가로 부여하지 않으면, 나누어 떨어지지 않는데 tmp[-1] // 3 == nums[idx]의 결과가 우연히 일치하는 경우가 예외로 발생할 수 있기 때문에 꼭 위 조건을 포함해주어야 합니다.
모든 재귀가 종료되면 result 변수에는 수열 A가 포함되어있어야 합니다.(문제에서 보장하므로) 해당 수열을 출력하여 문제를 마무리 했습니다.
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
