[파이썬/python] 백준 - 33633 3교시: 수학

문제

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

---

문제 설명

1. 길이가 N인 우박수열 $A_1,A_2,,A_3,..., A_N$을 만들려고 한다.
2. 우박수열은 다음 조건을 만족하는 수열 A이다.
   1. $ 1 ≤ i < N$ 인 양의 정수 i에 대하여 $A_i$가 짝수라면 $A_{i+1} = A_i/2$, 홀수라면 $A_{i+1} = 3A_i + 1$이다.
   2. $A_N = 1$이다. 또한 $1 ≤ i < N$이면 $A_i ≠ 1$이다.
3. N이 주어질 때 가능한 길이가 N인 우박수열의 개수를 구하고, 가능한 우박수열의 $A_1$을 오름차순으로 출력한다.

 

---

풀이

처음에 문제를 잘못 이해해서 시간이 꽤 걸렸다.
그래서 헷갈리지 않도록 먼저 문제를 정확히 이해하고 넘어가자.

 

헷갈렸던 부분은 A의 각 원소가 양의 정수인가? 하는 점이었다.

 

문제에서는 “양의 정수 i에 대하여”라고만 나와 있고,
$A_i$가 양의 정수인지 명확하게 적혀 있지 않았다.
그래서 분수나 음수도 가능한가 고민했다.

 

하지만 문제에서 짝수와 홀수로 구분하고 있고,
또 수열의 구조상 음수가 나올 수 없기 때문에 $A_i$는 양의 정수라고 판단하고 풀이를 진행했다.

 

N = 8일 때 몇 개의 항을 구해보자.

 

먼저 $A_8 = 1$이라는 정보가 주어져 있다.
이를 통해 $A_7$을 어떻게 구할 수 있을까?

 

문제에서 주어진 수식을 이용해 계산해 보면 다음과 같다.

• $A_7$이 짝수인 경우
  $A_8 = A_7 / 2$ 이므로
  $A_7 = 2$ 이다.
  2는 짝수이므로 조건을 만족한다.
  
  
• $A_7$이 홀수인 경우
  $A_8 = 3A_7 + 1$ 이므로
  $A_7 = 0$이다.
  하지만 0은 짝수가 되어 조건을 만족하지 않는다.

따라서 $A_7 = 2$이다.

 

다음으로 $A_6$을 구해보자.

• $A_6$이 짝수인 경우
  $A_7 = A_6 / 2$ 이므로
  $A_6 = 4$이다.
  4는 짝수이므로 조건을 만족한다.
  
  
• $A_6$이 홀수인 경우
  $A_7 = 3A_6 + 1$ 이므로
  $A_6 = 1/3$이다.
  1/3은 정수가 아니므로 짝수/홀수 조건을 만족할 수 없다.

따라서 $A_6 = 4$이다.

 

다음으로 $A_5$를 구해보자.

• $A_5$가 짝수인 경우
  $A_6 = A_5 / 2$ 이므로
  $A_5 = 8$이다.
  8은 짝수이므로 조건을 만족한다.
  
  
• $A_5$가 홀수인 경우
  $A_6 = 3A_5 + 1$ 이므로
  $A_5 = 1$이다.
  1은 홀수이므로 조건을 만족한다.

따라서 $A_5$의 값은 [1, 8]이 된다.

 

이와 같은 방식으로 역으로 계산을 반복하면 $A_1$의 가능한 값을 모두 구할 수 있다.

 

나는 이를 재귀 방식으로 구현했다.

 

각 단계에서

• 짝수 조건을 만족하는 값
• 홀수 조건을 만족하는 값

두 가지 경우를 모두 계산한 뒤,
해당 값이 문제의 조건을 만족하는지 확인하며 재귀적으로 탐색했다.

 

또한 $A_N$을 제외한 나머지 값들은 1이 될 수 없기 때문에
이 부분에 대한 예외 처리를 추가했다.

 

최종적으로 가능한 모든 값을 배열에 저장한 뒤 정렬하여 결과를 출력했다.

 

코드

import sys
input = sys.stdin.readline

N = int(input())

res = []

def solve(i, n):
    global res
    if i == 1:
        res.append(n)
        return
    
    A0 = 2*n
    A1 = (n-1) / 3

    if A0 != 1 and A0 % 2 == 0:
        solve(i-1, A0)
    if A1 != 1 and A1 % 2 == 1:
        solve(i-1, int(A1))

solve(N, 1)
res.sort()

print(len(res))
for i in res:
    print(i)

---

시간복잡도

 

이 문제는 최악의 경우 $N = 55$이다. 분기가 $A_i$마다 2갈래로 분기되기 때문에 총 $2^{55} = 10^{15}$정도의 시간복잡도를 가져야 정상이다. 1초는 약 $10^8$이기 때문에 시간초과가 나야한다.

 

하지만 통과한 이유는 문제의 조건때문이다. 두 번째 조건인 $(n-1)/3$는 값이 홀수로 나와야 다음 재귀로 넘어갈 수 있기 때문에 조건을 만족하는 경우가 매우 미미하다

 

따라서 해당 조건일 때 나올 수 있는 분기 수를 확인해보니 2배가 아닌 약 1.25배로 분기가 된다고 한다

 

따라서 $(1.25)^{55} = 6*10^5$정도의 시간복잡도를 예상해볼 수 있다

 

문제를 풀어보고 든 생각은 사실 재귀가 아니라 BFS같은 방법을 통해 방문처리를 진행한다면 처음부터 문제를 방지할 수 있겠구나 싶었다.