백준(BOJ) 2448 별 찍기 - 11(Python)

문제 내용

 

단순한 재귀 문제.

지겹도록 보는 프랙탈 구조를 재귀로 표현하면 된다.

처음에는 줄마다 출력할려고 했으나, 그러면 이런저런 조건이 많이 붙어야 할 것 같아 귀찮아서 패스했다.

그렇게 생각한게 그냥 2차원 리스트 안에 텍스트를 다 집어넣고 한 번에 출력하는 방식이다.

일종의 분할 정복이라고 볼 수 있을 것 같다.

3*2^n 형태로 입력을 받는데, 세로 길이는 3*2^n이고 가로 길이는 공백 포함 6*2^n-1이다.

최소 단위의 삼각형을 기준으로 프랙탈이 총 n번 이루어지기 때문에, n회 재귀를 실행했다.

​

코드는 다음과 같다.

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
#input=sys.stdin.readline
sys.setrecursionlimit(100000000)

def func(a,x,y):
    if a!=1:
        k=3*a//2
        func(a//2,x,y)
        func(a//2,x+3*a//2,y-k)
        func(a//2,x+3*a//2,y+k)
    L[x][y]='*'
    L[x+1][y-1]='*'
    L[x+1][y+1]='*'
    L[x+2][y-2]='*'
    L[x+2][y-1]='*'
    L[x+2][y]='*'
    L[x+2][y+1]='*'
    L[x+2][y+2]='*'

n=int(input())
k=n//3
L=[[' ' for i in range(6*k-1)] for j in range(n)]
func(k,0,(6*k-1)//2)
for i in L:
    print(''.join(i)

이런 별 찍기 문제는 풀어서 설명하기가 참 모호한 것 같다.

특히 이놈의 Trial and Error 때문에 더 그런 것 같다.

혹시나 재귀 횟수 때문에 걸릴까봐 sys.setrecursionlimit(100000000)을 코드 맨 위에 추가했는데, 이는 기본적인 파이썬의 최대 재귀 제한인 1000회를 임의로 100000000회로 변경하는 코드이다. 재귀 문제를 풀 때 웬만해선 꼭 이 코드를 위에 추가하는 편이다.

input=sys.stdin.readline

sys.setrecursionlimit(100000000)

이 두 코드는 항상 백준 코드에서 맨 위에 주석으로 처리해두고, 제출했을 때 시간 초과나 재귀 한도 초과가 발생하면 주석을 해제해서 다시 제출해본다.