https://www.acmicpc.net/problem/2447
2447번: 별 찍기 - 10
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이
www.acmicpc.net
풀이1
(3^k)꼴의 N과 3x3 패턴의 출력 형식이 주어졌을 때, 그 패턴에 맞춰 NxN 크기로 별을 출력하는 문제였다.
NxN은 (N/3) x (N/3) 크기의 영역 9개로 이루어져 있으며, 그 나누어진 영역은 다시 9개의 더 작은 영역으로 이루어져 있다. 그래서 문제에서 주어진 것처럼, 재귀적인 분할 정복 방식을 사용하여 문제를 해결할 수 있다.
위 그림은 N = 9일 때를 나타낸 것이다. 만약 N = 27이라면 이 그림이 9개로 이루어져 있을 것이다.
즉, NxN을 그리기 위해선 (N/3) x (N/3) 9개를 그려야 하고, N/3을 다시 나누다 보면 결국 3x3 영역부터 그리기 시작해서 전체를 그리게 된다.
참고로 영역은 배열을 사용하여,
가장 왼쪽 상단의 시작점(row, col)과 영역의 크기(size)를 통해 영역을 나타낼 수 있다.
그러면 이제 NxN 패턴의 별을 그리는 재귀 함수를 선언하고, 그 안에서 크기가 3이 될 때까지 (N/3) x (N/3) 영역 9개 그리도록 재귀적으로 호출하면 문제를 해결할 수 있다.
위의 과정에서 영역을 인자로 받아서 3x3패턴의 별을 배열에 저장해주는 함수와 공백을 저장하는 함수가 추가적으로 필요하다.
풀이2
풀이1은 영역을 중심으로 분할해서 가장 작은 단위부터 해결하는 방식이었다. 다른 방법은 없을까 궁금해서 다른 분들의 풀이를 살펴보다가, 같은 분할 정복이지만 약간 다른 관점의 방법이 있어서 소개하려고 한다.
이 방법도 어느 영역에 속하는지가 중요하긴 하지만, 영역 자체가 아닌 각 점이 어느 영역에 속하는지 판단하여 해당 위치에 '*' 이나 ' '를 저장한다.
우선, 기본 단위인 3x3에서 빈칸은 각 정사각형의 1행 1열에 해당한다. 좌표는 (1,1), (1, 4), (1, 7), (1, 10), (1, 13)이며,
판별식은 (i % 3 == 1) && (j % 3 == 1)이다.
9x9 패턴에서도 공백은 3x3 단위로 봤을 때 1행 1열 영역에 해당한다.
즉, N x N 패턴에서 1행 1열에 있는 (3/N) x (3/N) 영역 전부가 공백에 해당한다.
그리고 모든 크기로 확장한 판별식은 {(i / size) % 3} == 1 && {(j / size) % 3} == 1이 된다.
i / size 은 그 점이 3*size x 3*size 단위로 봤을 때, 몇 번째 행의 size x size 영역인지를 나타낸다.
예를 들어 N = 27, size = 9, i = 11, j = 0이라면,
i / (size/3) = 3이므로 위에서 네 번째 3x3 영역에 속하며,
3 % 3 = 0이므로 9x9 영역에서 0행 0열에 있는 3x3에 속한다. 즉 1행 1열이 아니기 때문에 공백이 아닌걸 알 수 있다.
그리고 이것을 재귀적 코드로 나타내면 아래와 같다.
코드1
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val stars = Array(n) { CharArray(n) }
setStars(stars, 0, 0, n) // NxN 패턴 별을 그린다
val answer = StringBuilder()
stars.forEach { charArray ->
charArray.forEach {
answer.append(it)
}
answer.appendLine()
}
print(answer)
}
// 왼쪽 위의 점인 stars[row][col]에서부터 size * size만큼 별 저장
fun setStars(stars: Array<CharArray>, row: Int, col: Int, size: Int) {
// 크기가 3일 때까지 나누어 들어가다가, 3이 되면 해당 영역에 3x3 패턴을 저장하고 종료한다.
if (size == 3) {
set3Pattern(stars, row, col, size)
return
}
val dividedSize = size / 3
// 0행
setStars(stars, row, col, dividedSize)
setStars(stars, row, col + dividedSize, dividedSize)
setStars(stars, row, col + 2*dividedSize, dividedSize)
// 1행
setStars(stars, row + dividedSize, col, dividedSize)
setSpace(stars, row + dividedSize, col + dividedSize, dividedSize) // 공백
setStars(stars, row + dividedSize, col + 2*dividedSize, dividedSize)
// 2행
setStars(stars, row + 2*dividedSize, col, dividedSize)
setStars(stars, row + 2*dividedSize, col + dividedSize, dividedSize)
setStars(stars, row + 2*dividedSize, col + 2*dividedSize, dividedSize)
}
// 3 * 3 패턴 별 저장
fun set3Pattern(stars: Array<CharArray>, startRow: Int, startCol: Int, size: Int) {
for (row in startRow until startRow + size){
for (col in startCol until startCol + size){
stars[row][col] = '*'
}
}
stars[startRow + 1][startCol + 1] = ' '
}
// 공백 저장
fun setSpace(stars: Array<CharArray>, startRow: Int, startCol: Int, size: Int) {
for (row in startRow until startRow + size){
for (col in startCol until startCol + size){
stars[row][col] = ' '
}
}
}코드2
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val answer = StringBuilder()
for (i in 0 until n) {
for (j in 0 until n) {
answer.append(getStar(i, j, n / 3)) // 위치에 해당하는 '*' or ' ' 반환
}
answer.appendLine()
}
print(answer)
}
fun getStar(row: Int, col: Int, size: Int): Char {
// 해당 위치가 (3*size) * (3*size)의 정사각형 영역 안에서,
// 가운데 영역인 (size * size) 정사각형 안에 포함될 경우
if ((row / size) % 3 == 1 && (col / size) % 3 == 1){
return ' '
}
return if (size == 1) '*'
else getStar(row, col, size / 3)
}'Problem Solving > 백준' 카테고리의 다른 글
| 백준 1783번: 병든 나이트 (Kotlin) (0) | 2022.01.06 |
|---|---|
| 백준 1517번: 버블 소트 (Kotlin) (0) | 2022.01.05 |
| 백준 1780번: 종이의 개수 (Kotlin) (0) | 2021.12.30 |
| 백준 1654번: 랜선 자르기 (Kotlin) (0) | 2021.12.27 |
| 백준 1167번: 트리의 지름 (0) | 2021.12.25 |
