[백준] 2447, 11729 - Python3

2447. 별 찍기 - 10

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

내 풀이 - 성공

from sys import stdin

N = int(stdin.readline())

arr = [["*"]*N for i in range(N)]

def func(si, sj, ei, ej, n):
    if si == ei or sj == ej:
        return

    tmp = n // 3
    
    for i in range(tmp):
        for j in range(tmp):
            arr[si+tmp+i][sj+tmp+j] = " "
    
    if n != 1:
        func(si, sj, si+tmp, sj+tmp, tmp)
        func(si+tmp, sj, si+tmp*2, sj+tmp, tmp)
        func(si+tmp*2, sj, ei, sj+tmp, tmp)
        
        func(si, sj+tmp, si+tmp, sj+tmp*2, tmp)
        func(si+tmp*2, sj+tmp, ei, sj+tmp*2, tmp)
        
        func(si, sj+tmp*2, si+tmp, ej, tmp)
        func(si+tmp, sj+tmp*2, si+tmp*2, ej, tmp)
        func(si+tmp*2, sj+tmp*2, ei, ej, tmp)

func(0, 0, N, N, N)

for i in range(N):
    for j in range(N):
        print(arr[i][j] ,end='')
    print()

3 * 3 기본 모양을 기준으로 분할정복 이용

arr 리스트에 우선 * 로 채워두고
재귀를 돌면서 가운데 부분만 빈칸으로 지워줌

3 분의 1 로 나눈 값을 가지고 9 개의 구역으로 나눠서 재귀 돌리기

---

11729. 하노이 탑 이동 순서

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

다른 사람의 풀이

from sys import stdin

N = int(stdin.readline())

def hanoi(n, start, end) :
    if n == 1 :
        print(start, end)
        return
       
    hanoi(n-1, start, 6-start-end)	# 1
    print(start, end)			# 2
    hanoi(n-1, 6-start-end, end)	# 3

print(2**N - 1)
hanoi(N, 1, 3)

마지막 N 번째 원판이 3 번째 기둥으로 가려면 N-1 개의 원판들은 2 번째에 있어야 한다
는 점을 이용

따라서
1. start 기둥에 있는 N-1 개의 원판들을 보조 기둥으로 모두 이동
2. N 번째 원판을 start -> end 로 이동
3. 보조 기둥에 있는 N-1 개의 원판들을 end 기둥으로 모두 이동

의 절차를 수행하면 된다.

6-start-end : 1, 2, 3 중 사용하지 않은 한가지의 탑을 찾아줌