-
[백준/Python] 2447번: 별 찍기 - 10 풀이 ★Coding Test/Baekjoon 2021. 5. 15. 20:42
내가 이 문제로 끙끙대서 스스로 실망했다... 고작 별 찍기에 무너지다니ㅠㅠ
출처: https://www.acmicpc.net/problem/2447
문제
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.
크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
*** * * ***
N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.
입력
첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
출력
첫째 줄부터 N번째 줄까지 별을 출력한다.
풀이 방법
풀이 1
모든 별찍기는 9등분할 수 있다. 정가운데는 공백이고 그 외는 하위 별찍기 패턴이 반복된다. 이를 이용하여 재귀를 하면 문제를 풀 수 있다.
- ' '로 채워진 n x n 크기의 2차원 배열 picture를 만든다.
- _n ==1인 경우 picture[y][x]='*'로 저장한다.
- i는 0부터 2까지, j는 0부터 2까지(전체를 9등분)
- i와 j 모두 1이면 가운데 칸이므로 pass
- 아니면 하위 별찍기 함수를 재귀한다.
참고: [2447번] 별찍기 10 - BOJ : 네이버 블로그 (naver.com)
풀이 2
위의 별찍기를 보면 정가운데를 빼고 나머지 여덟 부분이 모두 동일하다는 것을 알 수 있다. 또한, 맨 위와 맨 아래는 동일하다. 따라서 top-middle-bottom으로 나누면 다음과 같다.
top == bottom = x x x
middle == x 공백 x
재귀 시 top&bottom, middle로 나누어 풀 수도 있다.
참고: 18303409번 소스 코드 (acmicpc.net)
코드
풀이 1
풀이 2
'Coding Test > Baekjoon' 카테고리의 다른 글
[백준/Python] 1427번: 소트인사이드 풀이 (0) 2021.05.21 [백준/Python] 2798번: 블랙잭 풀이 (0) 2021.05.20 [백준/Python] 10870번: 피보나치 수 5 풀이 (0) 2021.05.15 [백준/Python] 16554번 소인수분해 풀이 (0) 2021.05.15 [백준/c++] 10757번: 큰 수 A+B (0) 2021.05.13