#2448:별 찍기 - 11 #백준 #파이썬 #재귀함수

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

2448번: 별 찍기 - 11

 

 

풀이

#2448 별찍기 11 code

2448번 문제는 별이 다음과 같은 형태로 출력을 하는 것이다. (다음 그림은 24)를 입력했을 때 나오는 출력형태이다.

출력형태 24입력

위 출력을 보면 재귀함수나 반복문을 통해 일정한 규칙으로 코드를 짜면 된다는 것을 알 수 있다. 나는 재귀함수으로 문제풀이를 접근했다. 일단 입력 값은 3*2**n = size 으로 (3,6,12,24...)으로 주어진다. size에 3이 주어지면 가장 작은 단위인 삼각형 하나가 출력이 되고,  size = 6인 경우 삼각형 3개가 삼각형 틀 안에 들어간 형식으로 주어진다. size = 12 인 경우는 size = 6인 삼각형이 3개가 모여 삼각형 틀안에 들어간 형식이 된다. 

size = 3

size = 6

size = 12

 

이런 규칙을 찾았다면 이제 문제를 재귀로 문제를 풀 수 있다는 것을 알 수 있다.  가장 작은 단위인 사이즈가 3인 삼각형이 사이즈 6에 3개가 들어가는 것이고 사이즈 12인 삼각형은 사이즈가 6인 삼각혀잉 3개가 들어간다는 것을 알 수 있다. 

사이즈 1 삼각형은 좌표로 나타내면 1단계 (0,2) , 2단계 (1,1),(1,3), 3단계(2,0)......(2,4)에 별이 들어간다는 것을 알 수 있다.  이것을 통해 사이즈 3인 삼각형을

       data[y][x] = "*"

        data[y+1][x-1] = data[y+1][x+1] = "*"

        for i in range(-2,3):

            data[y+2][x+i] = "*"

(x,y는 시작점 즉 (0,2))

 

이렇게 구현할 수 있고,

 

그리고 사이즈 6 삼각형을 보면 작은 삼각형이 시작점이 3개로 나뉘는 것을 볼 수 있다. (0,2) , (3,-1),(3,5) 이 부분을 보면 재귀함수로 들어갈 때 인자값을 

(시작점(y,x)라고 하자.)'

 

다음 인자값 사이즈 = 현재 사이즈//2

 

-(0,2)경우의 시작점

(y, x)

 

-(3,-1)경우의 시작점

(y+ 다음 인자값 사이즈, x-다음 인자값 사이즈)

 

-(3,5)경우의 시작점

(y+ 다음 인자값 사이즈, x+다음 인자값 사이즈)

 

이렇게 3가지로 생각 할 수 있다. 이 3가지가 계속 반복되는 형태이다.

따라서

        NextN = n // 2

        recursive(y, x, NextN)

        recursive(y + NextN, x - NextN, NextN)

        recursive(y + NextN, x + NextN, NextN)

 

이렇게 코드를 만들 수 있다.

 

즉 종합해보면

재귀 함수에 사이즈, 좌표를 입력 받아야한다.

사이즈와 좌표를 입력 받고, 이 사이즈가 3인 경우 가장 작은 삼각형을 총 출력 data에 입력한다. 

아닌 경우에는 사이즈//2를 하고 재귀함수를 통해 각 세개의 나뉜 시작좌표로 넘어간다. 그렇게 n이 3이 될 때 까지 계속 반복하여 총 출력 data에 입력하면 해당 입력값에 맞는 출력 형태를 반환할 수 있다. 

n = int(input())

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

def recursive(y, x, n):

    if n == 3:

        data[y][x] = "*"

        data[y+1][x-1] = data[y+1][x+1] = "*"

        for i in range(-2,3):

            data[y+2][x+i] = "*"

   

    else:

        NextN = n // 2

        recursive(y, x, NextN)

        recursive(y + NextN, x - NextN, NextN)

        recursive(y + NextN, x + NextN, NextN)

recursive(0, n-1, n)

for i in data:

    print("".join(i))

 

밤이라서 졸려서 너무 중구난방으로 글을 쓴 것 같은데.... 그래도 코드 자체는 쉽기 때문에 대충 읽어보셔도 이해하실 겁니다.... 모두 즐코딩하세용