백준 1769 3의 배수 - python

첫 번째 코드(시간 초과)

X = int(input())
cnt = 0
def f(a):
    global cnt
    if 1 <= a <= 9:
        if a % 3 == 0:
            print(cnt)
            print('YES')
            return
        else:
            print(cnt)
            print('NO')
            return
    else:
        t = 0
        for i in range(len(str(a))):
            t += int(str(a)[i])
        a = t
        cnt += 1
        f(a)
f(X)

두 번째 코드(성공)

X = input()
cnt = 0
def f(a):
    global cnt
    if len(a) == 1:
        if int(a) % 3 == 0:
            print(cnt)
            print('YES')
            return
        else:
            print(cnt)
            print('NO')
            return
    else:
        t = 0
        for i in range(len(a)):
            t += int(a[i])
        a = str(t)
        cnt += 1
        f(a)
f(X)

int에서 str로 바꾸는 str()은 O(log n)의 시간 복잡도를 가집니다. (O(log n) = O(d) => n이라는 파라미터의 자릿수(d)에 비례)

입력이 최대 1000000자리인데 int형으로 입력받은 뒤 str로 for 문에 집어넣었기 때문에 시간 초과가 났었습니다.