[백준 2448번] 별 찍기 - 11 - python

문제 링크

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

2448번: 별 찍기 - 11

 

풀이 

- 재귀 함수, 분할 정복 문제

이 문제의 핵심은,

n 일 경우 n // 2 의 삼각형 3개로 분리가 가능하다는 것이다. 

 

예를 들어 

n 은 6일 때, n 은 3일 때의 삼각형 3개로 분리

n 은 12일 때, n 은 6일 때의 삼각형 3개로 분리

... 

따라서 n이 3일 때는 삼각형을 그리고,

나머지 경우에 대해서는 3개의 삼각형으로 나누어 재귀 함수 호출 

 

나눌 때 좌표 값은 

        draw(x, y, size)
        draw(x+size,y-size,size)
        draw(x+size,y+size,size)
아래 그림에 표시된 좌표 번호 참고 

n = int(input())

graph = [ [" "] * 2*n for _ in range(n) ]

def draw(x, y, n):
    # 3일 때 삼각형 그리기 
    if n == 3 :
     	# 첫째줄 
        graph[x][y] = '*'
        # 둘째줄 
        graph[x+1][y-1] = graph[x+1][y+1] = '*'
        # 셋째줄 
        for i in range(-2, 3):
            graph[x+2][y+i] = "*"
    # 삼등분 
    else:
        size = n // 2 
        draw(x, y, size)
        draw(x+size,y-size,size)
        draw(x+size,y+size,size)

draw(0, n-1, n)

for i in graph:
    print("".join(i))