[python] 단계별로 풀어보기 - 10단계

 

 

 

전반적으로 풀이과정이 거의 유사하다

재귀함수에 대한 문제인데,  재귀함수는 정의 단계에서 자신을 재참조하는 함수이다.

그래서 식에 맞게 함수만 잘 선언해주면 바로 해결할 수 있는 단계!

 

 

---

 

 

10-1) 백준 10872번: 팩토리얼

 

def factorial(num):
    if num == 0:
        return 1
    return num*factorial(num-1)

n = int(input())
print(factorial(n))

 

n! = n*(n-1)*(n-2)*(n-3) ... 

 

 

 

 

​10-2) 백준 10870번: 피보나치 수5

 

def fibonacci(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    return fibonacci(num-1)+fibonacci(num-2)

n = int(input())
print(fibonacci(n))

 

n = (n-1) + (n-2)

​

​

​

 

 

10-3) 백준 12447번: 별 찍기-10

 

def stars(n):
    matrix=[]
    for i in range(3 * len(n)):
        if i // len(n) == 1:
            matrix.append(n[i % len(n)] + " " * len(n) + n[i % len(n)])
        else:
            matrix.append(n[i % len(n)] * 3)
    return(list(matrix))

star = ["***","* *","***"]
n = int(input())
k = 0
while n != 3:
    n = int(n / 3)
    k += 1
    
for i in range(k):
    star = stars(star)
for i in star:
    print(i)

 

사실 내가 직접 풀지는 못한 문제...!사실 내가 직접 풀지는 못한 문제...! 그래도 나름대로 공부를 해본 풀이를 적어보자면

만약 n=3이라고 생각하면 (1,1)의 위치에 있는 공간이 비었고,

n=9라면 가로, 세로 모두 (1,4,7)의 위치에 있는 공간이 비었다 => 3으로 나눈 나머지가 1인 곳

또한, 문제에서 확인할 수 있듯, 중간에 크게 빈 공간이 있는데 가로, 세로 모두 (3,4,5)에 해당하는 공간이 비어있다

=> 3으로 나눈 몫이 1인 곳

​

그래서 n=9일때를 생각하면 n=3일 때를 9개 붙인다 생각하고, 모두 빈 공간만 잘 생각해서 푸는 것 같음...!

 

 

 

 

 

 

10-4) 백준 11729번: 하노이 탑 이동 순서

 

def Hanoi(n,a,b,c):
    cnt = 0
    if n == 1:
        print(a,c)

    else:
        Hanoi(n-1, a, c, b)
        print(a,c)
        Hanoi(n-1, b, a, c)


n = int(input())
print(2**n-1)
Hanoi(n,1,2,3)

 

하노이 탑 이동 횟수 구하는 공식: 2^n - 1

​