백준 2448번: 별찍기 - 11

문제링크:2448번: 별 찍기 - 11 (acmicpc.net)

2448번: 별 찍기 - 11

 

이 문제는 별다른 설명 없이 예제 케이스를 보고 3*2^k 에 대한 별 찍기를 가능하게 하는 코드를 만드는 문제이다. 여기서 입력값은 3*2^k (0<=k<=10)인 정수이다. 예제 케이스의 입력값인 24를 보면 k는 3이라는 것을 알 수 있다. k가 0일때는 밑변의 별의 개수가 5개인 삼각형 모양이 나오고 k가 1일때는 밑변의 별의 개수가 10개, 다음은 20 개 순서대로 2배씩 늘어나는 것을 생각 할 수 있다. 그런데 삼각형 모양을 어떻게 구현할 지 생각하다 리스트가 N개 들어있는 2차원 배열을 만든 후 각 리스트가 각 줄에 대응되게 만들고 공백을 0, 별이 들어갈 자리를 1로 대응시켜 재귀 함수를 통해 구현했다.

import sys
from collections import deque

N=int(sys.stdin.readline().rstrip())
lst=[[0 for i in range(N-1-j)] for j in range(N)]

def pyramid(size,startr,endr): #위에서부터 채워나가기 startr=시작줄 endr=끝줄
    half=size//2
    if size==3:
        lst[startr].append(1)
        lst[startr+1].append(1)
        lst[startr+1].append(0)
        lst[startr+1].append(1)
        for _ in range(5):
            lst[startr+2].append(1)
        return
        
    pyramid(size//2,startr,startr+half)
    pyramid(size//2,startr+half,endr)
    for i in range(startr+half,endr):
        for _ in range(2*(endr-1-i)+1):
            lst[i].append(0)
    pyramid(size//2,startr+half,endr)

pyramid(N,0,N)

for i in range(N):
    for j in range(N-1-i):
        lst[i].append(0)
            

for i in range(N):
    for j in lst[i]:
        if j==0:
            print(' ',end='')
        if j==1:
            print('*',end='')
    print()

만든 함수 pyramid는 입력값으로 삼각형의 size, 삼각형 모양 입력을 시작할 줄 startr, 마칠 줄 endr를 받는다. 위에 말한 규칙대로 삼각형 내부의 삼각형은 1/2 씩 줄어드므로 마지막 size인 size가 3이 아니라면 size가 절반이 된 시작과 끝인 startr,startr+half인 삼각형을 (삼각형을 4개로 나눴을 때 가장 위의 삼각형) 재귀로 먼저 호출하고, 다음은 size가 절반이고 startr+half,endr인 삼각형 (삼각형을 4개로 나눴을 때 아래 왼쪽의 삼각형) 호출, 다음은 삼각형을 4개로 나눴을때 가운데  공백인 삼각형을 리스트에 0을 입력해주어 공백으로 처리하고 마지막으로 다시 size가 절반이고 startr+half,endr인 삼각형 (삼각형을 4개로 나눴을때 아래 오른쪽 삼각형) 재귀로 호출해 주었다.

 

특이사항으로는 공백인 삼각형은 자세히 보면 맨 밑에 공백이 한자리 있고, 공백이 밑에서부터 1, 3, 5, 7... (2*half-1)개 만큼 있으므로 잘 생각해서 구현해준다. 그리고 size가 3인 경우가 마지막 경우이므로 시작줄부터 시작+2줄까지 (*),(* *),(*****)를 각각 입력해준다.

 

그러면 공백을 0으로 처리하고 별이 들어갈 위치를 1로 처리한 리스트가 생성되는데 0을 공백으로, 1을 별로 출력해서 백준에 입력하면 출력 형식이 잘못되었다고 나오게 된다. 질문 게시판을 찾아보니 각 열의 별 뒷부분에도 공백 처리를 해줘야 한다고 해서 리스트의 빈 부분만큼 0을 채워주고 입력하면 된다.