문제링크
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번째 줄까지 별을 출력한다.
조건
- 시간 제한 : 1s
- 메모리 제한 : 256MB
해설
처음 문제를 보고나서 2가지 방법이 생각났는데, 하나는 출력할 문자들을 담을 배열에 ‘*’을 가득 채워놓고, 공백에 해당하는 원소의 값을 규칙에 맞게 수정하는 방법이고, 나머지 하나는 아래에서 사용할 각 출력될 문자의 위치에 따라 ‘*’을 출력할지, 공백을 출력할 지를 결정해 출력하는 방법이다.
3X3, 9x9 문양일 때를 잘 보면, 기본적으로 3으로 나누었을 때 → 1 / 4 / 7 이 공백이 되고, 9로 나누었을 때 → 3 / 4 / 5 가 공백이 된다. 여기에서 규칙을 찾아보면, 행과 열에 N/3으로 나눈 몫을 3으로 나누었을 때 나머지가 1인 행과 열에서 공백이 출력된다.
0 1 2 3 4 5 6 7 8
0 * * * * * * * * *
1 * * * * * *
2 * * * * * * * * *
3 * * * * * *
4 * * * *
5 * * * * * *
6 * * * * * * * * *
7 * * * * * *
8 * * * * * * * * *
풀이
위 설명을 코드로 구현하면 아래와 같다. 실질적으로 실제 N이 27이라면, 출력은 함수에 N이 9로 들어왔을 때 출력이 실행된다. 행과 열을 N으로 나눈 몫에 3을 나눈 나머지가 1 (→ 3등분 하여 중간 값들을 선택함)인 경우에 공백을 출력하고, 그게 아니라면 또다시 N을 3으로 나누고 함수를 재귀 호출한다. N 값이 1이라면 (더이상 블럭을 등분할 수 없다면) *을 출력한다.
void pattern(int row, int column, int N) {
if((row / N) % 3 == 1 && (column / N) % 3 == 1) {
cout << ' ';
} else {
if(N / 3 == 0) {
cout << '*';
} else {
pattern(row, column, N/3);
}
}
}
코멘트
별 찍기 문제 주제에 생각보다 어려웠다. 진짜로... ㅋㅋㅋ
고민
처음에는 아래 코드처럼 구현했는데, 생각보다 많이 복잡해보이더라. 그래서 정답 제출 코드들을 참고하여 더 아래에 있는 ‘코드’ 처럼 개선을 하였다.
#include <iostream>
using namespace std;
void pattern(int row, int column, int N) {
if(N == 3) {
if(row % N == 1 && column % N == 1) {
cout << ' ';
} else {
cout << '*';
}
} else if((row / (N/3))%3 == 1 && (column / (N/3))%3 == 1) {
cout << ' ';
} else {
pattern(row, column, N/3);
}
}
int main() {
int N;
cin >> N;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
pattern(i, j, N);
}
cout << '\n';
}
return 0;
}
코드
#include <iostream>
using namespace std;
void pattern(int row, int column, int N) {
if((row / N) % 3 == 1 && (column / N) % 3 == 1) {
cout << ' ';
} else {
if(N / 3 == 0) {
cout << '*';
} else {
pattern(row, column, N/3);
}
}
}
int main() {
int N;
cin >> N;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
pattern(i, j, N);
}
cout << '\n';
}
return 0;
}
Uploaded by Notion2Tistory v1.1.0