개발 공부/알고리즘 문제풀이

[백준] 2447. 별 찍기 - 10

5묘 2022. 8. 2. 18:55
 

2447번: 별 찍기 - 10

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이

www.acmicpc.net


이번 문제는 정말 어려웠다...! 한참을 고민해도 답을 찾지 못해서, 푸신 분들의 블로그를 찾다가 재귀를 활용해 굉장히 간단하게 구현하신데다 설명도 이해하기 쉽게 써주신 분의 블로그를 참조해 문제를 풀 수 있었다!(https://mgyo.tistory.com/183)

 

[백준] 2447번 별찍기 문제 재귀 함수 이용해서 풀기

문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N*N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에

mgyo.tistory.com

풀이

별을 당장 찍는 방식이 아니라, 미리 0과 1로 구성된 이차원 배열을 만들고 재귀 함수를 이용해 별이 찍힐 위치만 1로 표시한 뒤, 나중에 해당 배열을 출력하며 1은 '*'로, 0은 공백으로 출력하는 방법이었다.

재귀 방식도 간단했는데, map의 [0][3:6], map의 [0][6:9]..이렇게 열(x값)에 3씩 더한 값이 map의 [0][:3] 과 동일하고, map[3][0:3], map[6][0:3] 이렇게 행(y값)에 3씩 더한 값도 map[0][:3]과 동일하기 때문에 N==3일 때의 패턴만 알면 규칙성을 이용해 나머지 패턴을 모두 구할 수 있는 원리였다.

 

# 2447. 별 찍기 - 10 2792ms https://mgyo.tistory.com/183 참고
def recursion(N):
    global map
    if N == 3:
        map[0][:3] = map[2][:3] = [1, 1, 1]
        map[1][:3] = [1, 0, 1]
        return
    else:
        a = N // 3
        recursion(N // 3)
        for i in range(3):
            for j in range(3):
                if i == 1 and j == 1:
                    continue
                for k in range(a):
                    map[a * i + k][a * j: a * (j + 1)] = map[k][:a]

        return

N = int(input())
map = [[0 for _ in range(N)] for z in range(N)]
recursion(N)
for y in range(N):
    for x in range(N):
        if map[y][x] == 1:
            print('*', end='')
        else:
            print(' ', end='')
    print()

굉장히 어려운 문제였지만, 규칙성을 찾으려고 노력한다면 그렇게 어렵지 않을 수도 있다는 것을 느낀 문제!
(하지만 그 규칙성을 찾아내는 게 원래 제일 어려운 일이지..ㅠ)