[백준] 2448 별 찍기 - 11 (Python 파이썬)

문제 설명

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

2448번: 별 찍기 - 11

문제의 별찍기 패턴을 보고 규칙을 유추하여 코드를 작성하는 문제이다.

---

풀이 과정

먼저, 백준에서 정답을 얻기 위해서는 공백을 포함한 그래프 전체를 출력해야 한다.

( 이 부분은 백준님이 정답코드를 잘못 기입하신 문제라고 한다. )

즉, N=24인 별찍기를 할 때 맨위에 별이 가운데 하나있을 때에도 양 옆으로 11개씩 공백을 모두 출력해야 한다.

 

처음 코드를 제출했을 때, 이 부분을 구현하지 않아 출력형식이 잘못되었다는 오류 결과를 받았다.

그래서, 별이 몇개든지 간에 별이 없는칸은 무조건 공백이 나오도록 코드를 수정하였다.

 

이 부분을 해결하면서 두 가지 풀이로 모두 풀어보았다.

 

풀이를 보기 전, 다음 규칙을 알고 보는것이 도움이 될 것이다.

N = 6

현재의 별찍기 모양은, 이전 별찍기 모양을 좌우로 두배 복사한 모양이다.

그래서 N = 6일 때는, N = 3 일때의 별모양이 양 옆으로 복사가 된 모습이다.

 

N = 12

마찬가지로, N = 12일 때는 N = 6의 별모양이 양옆으로 복사가 되어 나타난다.

이 규칙을 인지하고 풀이를 보면 이해하기 훨씬 수월할 것이다.

 

풀이①

먼저 n=3일 때는 가장 기본모형이므로 재귀문을 돌지않고 바로 출력하도록 하였다.

n=6일 때 부터 재귀문을 돌게되는데,

 

before는 이전 별찍기 모양, after는 현재 별찍기 모양을 저장한 리스트이다.

N줄 까지는 이전 별찍기 모양을 그대로 복사하면 되는데,

 

이 때, 백준제출을 성공하기 위해선 별을 제외한 양옆의 모든 칸을 공백으로 채워야 한다.

그래서 범위를 반드시 [N : (N+2*N) - 1] 으로 명시하여 지정한 부분 외에는 공백을 지키도록 해야한다.

 

N줄부터 2N줄까지는 이전 그래프의 모양을 양 옆으로 복사를 해야한다.

마찬가지로 공백을 지켜야 하기 때문에 범위 제한에 신경을 써주어야 한다.

 

이러한 방식으로 마지막 줄에 도착할 때 까지 계속 재귀를 돌려주면 된다.

n = int(input())

graph = [[" ", " ", "*", " ", " "], [" ", "*", " ", "*", " "], ["*", "*", "*", "*", "*"]]


def recursive(N, before):
    after = [[" "] * (2 * 2 * N - 1) for _ in range(2 * N)]
    for i in range(N):
        after[i][N:N+2*N-1] = before[i]

    k = 0
    for i in range(N, 2 * N):
        after[i][:2*N] = before[k]
        after[i][2 * N:2 * N+len(before[k])] = before[k]
        k += 1

    if 2 * N == n:
        return after

    return recursive(2 * N, after)


if n == 3:
    result = graph
else:
    result = recursive(3, graph)

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

 

풀이②

풀이2는 풀이1처럼 이전그래프를 양옆으로 복사한다는 개념보다는

맨 처음 n = 3 일때의 그래프를 계속 양옆으로 복사해 나가는 방식이다.

 

n = 3일 때의 가장 기본모양을 바탕으로,

다음 모양부터는 좌표만을 계산하여 재귀적으로 그리면 된다.

풀이2

n = int(input())
graph = [[' '] * 2 * n for _ in range(n)]


def recursive(x, y, N):
    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:
        nextN = N // 2
        recursive(x, y, nextN)
        recursive(x + nextN, y - nextN, nextN)
        recursive(x + nextN, y + nextN, nextN)


recursive(0, n - 1, n)
for i in graph:
    print("".join(i))

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !