[백준/python] 2447번 별찍기 - 10

1. 문제

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

 

문제는 3의 배수마다 사각형을 찍는다.

기본 패턴(아래 그림)을 반복하면 되지만 3 초과라면 중간에 공백이 들어간다.

# 3
***
* *
***

# 9
*********
* ** ** *
*********
***   ***
* *   * *
***   ***
*********
* ** ** *
*********

# 27
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

 

2. 문제 풀이

해결법은 대강 알았지만 코드 구현이 취약해서 다른 사람의 것을 보고 작성했다. 

문제 취지에 맞게 풀이하신 분의 블로그다.

https://developer-project.tistory.com/383

[백준] 2447번 : 별 찍기 - 10 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1) 코드

#https://www.acmicpc.net/problem/2447
# n = 9이면 가운데 공백 정사각형(n/3) * (n/3)
# 이 분것 참조
'''
*********
* ** ** *
*********
***   ***
* *   * *
***   ***
*********
* ** ** *
*********
'''

#분할정복으로 쪼개기 /3 으로 쪼개서 한줄씩 처리.
# n 27. 9*9 공백사각형을 크기 9패턴 둘러쌈.

def square(n):
    if n == 3:
        return ["***", "* *", "***"]
    pattern = square(n // 3)
    li = []

    for p in pattern:
        li.append(p * 3)
    for p in pattern:
        li.append(p + " " * (n//3) + p)
    for p in pattern:
        li.append(p * 3)
    return li

N = int(input())
print('\n'.join(square(N)))

 

2) 문제 파악

- 패턴

n = 27 사각형

사각형 예시를 보자. 패턴이 반복됨을 알 수 있다.

물론 n =3이면 아래 패턴은 무시되고 무조건 기본 패턴이다.

*패턴 공식
(n > 3)
기본 패턴 * n
기본 패턴 공백*(n//3) 기본패턴
기본 패턴 * n

 

그러면 우리는 빨간 부분(파란부분 * 3) 반복을 해주면 사각형을 찍을 수 있다!

 

-문제 알고리즘

같은 패턴이 하위 문제에서도 반복되므로 분할 정복 문제다. 

분할 정복 문제는 보통 재귀 함수를 사용한다. 

 

-코드 상세 분석

sqaure 함수를 순차적으로 따라가보자.

 

if n == 3:
        return ["***", "* *", "***"]

파라미터 n이 3일 경우 기본 패턴을 반환.

N(입력) = 3 이거나 재귀로 인한 최하위 층 방문이면 여기로 도달할 것이다.

N = 3이면 여기서 바로 함수는 종료된다. 

 

pattern = square(n // 3)

사각형은 3 제곱이다. 앞의 그림과 같이 사각형은 3배수 단위로 분할해야한다.

 

for p in pattern:
        li.append(p * 3)
    for p in pattern:
        li.append(p + " " * (n//3) + p)
    for p in pattern:
        li.append(p * 3)

여기 부분은 N(입력값) > 3 일 경우 실행된다. 이미 if 문에서 처리했기 때문. 

여기의 목적은 앞에서 설명했던 패턴공식을 리스트에 넣는 부분이다.

 

li는 이번단계 패턴 찍기고, pattern은 전단계 패턴이다.

 

for문의 구성은 현단계 패턴을 찍는다. 

• 기본 패턴 * n
• 기본 패턴 공백*(n//3) 기본패턴
• 기본 패턴 * n

이 결과는 li에 담기고 li는 최종 return이다.

 

후기

 3단 분할 까지는 파악했지만 이걸 어떻게 구현하는지를 모르겠어서 결국 답안을 보았었다.

내가 못푼 이유는 가장 작은 단위에서의 처리에서 꼬였기 때문에 

큰 단위 문제들도 못 푼 것으로 보인다.

 

분할정복 문제는 가장 작은 단위 문제부터 구현되는지 관찰해야 풀 수 있을 것 같다.