# 1. n-1개의 기둥을 B로 옮긴다. 
# 2. 1개의 기둥을 C로 옮긴다. 
# 3. n-1개의 기둥을 B에서 C로 옮긴다.

answer = 0
def hanoi(n, from_pos, to_pos, through_pos):
    global answer
    if n==1:
        answer += 1
        return
    hanoi(n-1, from_pos, through_pos, to_pos)
    answer += 1
    hanoi(n-1, through_pos, to_pos, from_pos)

# 풀이 1. 재귀 
# 시간 복잡도 - O(N^2) : 재귀로 두개의 분기가 계속해서 생기기 때문에 시간복잡도가 O(N^2)
def fibo(n):
    if n in (1,2):
        return 1
    return fibo(n-1) + fibo(n-2)

# 풀이 2. 동적 계획법
# 시간 복잡도 - O(N) 
def fibo(n):
    cache = [0,1]
    for i in range(2, n+1):
        cache.append(cache[i-1] + cache[i-2])

    return cache[n]

# 풀이 3. Memoization
fibo_cache = {}
def fibo(n):
    if n in fibo_cache:
        return fibo_cache[n]
    elif n == 1 or n == 2:
        value = 1
    elif n >= 2:
        value = fibo(n-2) + fibo(n-1)

    fibo_cache[n] = value
    return value

def gcd(x,y):
    if x < y:
        min_v = x
    else:
        min_v = y
    for i in range(min_v, -1, -1):
        if x%i == 0 and y%i == 0:
            return i

    return 'no'

# 유클리드 호제법
def gcd2(x,y):
    while y:
        # x을 y으로 나눈 나머지
        # 나머지가 0이 될때까지
        x,y = y,x%y
    return x

# 최소공배수
def lcm(x,y):
    if x < y:
        max = y
    else:
        max = x
    for i in range(max, x*y+1):
        if i%x == 0 and i%y == 0:
            return i
    return 'no'

# 유클리드 호제법
# X: AB, Y: CB , 최소공약수가 B라고 하자
# XY : ABBC
def lcm2(x,y):
    return x*y / (gcd2(x,y))

cache = {}
def factorial(n):
    if n in cache:
        return cache[n]
    elif n == 1:
        value = 1
    elif n >= 2:
        value = n*factorial(n-1)
    cache[n] = value
    return value

result = 0
for n in range(1,1000):
    if n % 3 == 0 or n % 5 == 0: # or가 포인트
        result += 1
print(result)

# 약수 판별하기
import math

def is_prime_num(n):
    for i in range(2, int(math.sqrt(n))+1): # n의 제곱근까지만 확인하면됨. 약수는 대칭적으로 존재하기 때문. int는 내림 효과가 있음
        if n % i == 0:
            return False
    return True

# 여러개의 소수를 판별해줘야 한다면? - 에라토스테네스의 체를 이용
def is_prime_num(n):
    arr = [True] * (n+1)
    for i in range(2, n+1):
        if arr[i] == True: # 특정 수가 지워지지 않았다면
            j = 2 # 2번째 배수부터
            while i*j <= n:
                arr[i*j] = False # i의 배수의 값을 False로 지워눚ㄴ다.
                j += 1
    return arr
arr = is_prime_num(50)