[Python/파이썬] 백준 2448번: 별 찍기 - 11

문제

 

풀이

왼쪽에서 오른쪽으로 분할!!

위 그림과 통해 규칙을 알 수 있다.

 

N = 6 -> N = 3일 때의 삼각형 3개로 분할 가능

N = 12 -> N = 6일 때의 삼각형 3개로 분할 가능

N = 24 -> N = 6일 때의 삼각형 3개로 분할 가능

...

 

N= 3인 경우 삼각형을 그린다.

아닐 경우, 이전 상태의 삼각형(N//2) 3개로 분할 (각각에 대해 재귀 호출)

 

 

1. 우선 전체 배열을 생성

stars = [[' ']*2*n for _ in range(n)]

 

2. 분할 정복을 위해 함수 생성 후 n이 3일 때 삼각형을 그려준다. i, j는 좌표 값

def recursion(i, j, size):
    if size == 3:
        stars[i][j] = '*'
        stars[i + 1][j - 1] = stars[i + 1][j + 1] = "*"
        for k in range(-2, 3):
            stars[i + 2][j - k] = "*"

 

3. 만약 n이 3이 아닌 경우 분할한다. 

else:
        newSize = size//2
        recursion(i, j, newSize)
        recursion(i + newSize, j - newSize, newSize)
        recursion(i + newSize, j + newSize, newSize)

 

4. 함수 호출 후 출력

recursion(0, n - 1, n)
for star in stars:
    print("".join(star))

 

N 이 6일때의 예시

세 좌표를 기준으로 분할

 

# N : 6
# newSize = 6 // 2 = 3
recursion(0, 5, newSize)
recursion(3, 5 - 3, newSize)
recursion(3, 5 + 3, newSize)

코드

import sys
input = sys.stdin.readline

n = int(input())

stars = [[' ']*2*n for _ in range(n)]

def recursion(i, j, size):
    if size == 3:
        stars[i][j] = '*'
        stars[i + 1][j - 1] = stars[i + 1][j + 1] = "*"
        for k in range(-2, 3):
            stars[i + 2][j - k] = "*"
    
    else:
        newSize = size//2
        recursion(i, j, newSize)
        recursion(i + newSize, j - newSize, newSize)
        recursion(i + newSize, j + newSize, newSize)

recursion(0, n - 1, n)
for star in stars:
    print("".join(star))

 

마무리

재귀는 너무 어렵다... 나중에 재귀 문제만 모아서 풀어봐야겠다.