[백준] 2448 - 별 찍기11

 

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

2448번: 별 찍기 - 11

문제 한줄 이해

- 별이 출력된 예제를 보고 규칙을 유추하기

생각난 풀이

1번째 방법: 어떤 규칙들이 있는지 생각했다.

1. 크게 일정 모양의 틀이 반복된다 -> 재귀다!

2. 입력되는 n이 무엇을 의미할까 -> 처음에는 일정하게 나타나는 삼각형 수인가? 삐이이이 !

                                                   -> 총 몇줄인지 인가? 그럴싸했다. 그렇다면 n의 따라 그래프가 그려지는건가? 라는 생각이 들었다.

                                                 -> 출력예제의 가로 길이도 확인하니 세로의 2배를 차지한다. -> 그렇다면 그래프는 n*(n*2)인거같은데..

3. 이제 그래프에 재귀를 통해 그려보자라는 생각을 했다.

 

이때 재귀는 어떻게 할지 분석을 해봤다.

우선 그림을 먼저 보자(난 항상 재귀는 그림이나 흐름을 그려가면서 파악하는게 이해하기 쉬웠다.)

그림에서 보면 먼저 파란선을 기준으로 3부분으로 나눠지고 나눠진 상태에서 빨간 선으로 3부분 ... 그안에서 또 검은선으로 3부분 ...

어어어?? 그전에 4 부분으로 나눠 분할정복했던 기억이 난다 !!!! 

그렇다면 처음 파란선을 기준으로 각 기준이 되는 맨위에 별들의 좌표를 비교 했을때 (0,23), (12,11), (12,35) 나눠진다.

이때 재귀에서 어떻게 인자를 넘겨 줘야 하는지 감이 온다.                    (0,23), (0+24//2,23-24//2), (0+24//2,23+24//2)

                                                                                                        (x,y), (x+n//2,y-n//2), (x+n//2,y+n//2)

다음으로 검정선을 보면 n=3이면 그려주면 된다.

따라서 다음과 같이 코드를 짰다.

import sys
n = int(sys.stdin.readline())
graph = [[" "for i in range(n*2)]for i in range(n)]

def draw(x,y,n):
    if n == 3:
        graph[x][y] = "*"
        graph[x + 1][y - 1] = "*"
        graph[x + 1][y + 1] = "*"
        for i in range(5):
            graph[x + 2][y - 2 + i] = "*"
        return
    draw(x,y,n//2)
    draw(x + n//2, y - n//2, n//2)
    draw(x + n//2, y + n//2, n//2)

draw(0,n-1,n)
for m in (graph):
    print("".join(m))

확실히 재귀는 그림을 그려서 규칙을 찾는게 좋은거 같다