백준 c++ 2447번 별찍기 - 10
문제 :
풀이 :
첫 번째 접근 : 모든 공백을 통해 규칙 살펴보기 ( X )
이렇게 모든 공백을 가정해보면 규칙이 눈에 들어오지 않는다.
생각을 해야한다.
일반화된 규칙을 찾아 재귀함수를 이용해 별을 찍을 수 있지 않을까
두 번째 접근 : 재귀함수를 이용해 분할해서 생각하기
(i, j, n)을 재귀함수가 받아 처리한다고 생각해보자
재귀함수를 이용해서 9 x 9 (n=9)일 때 i,j 좌표가 중앙일 때 공백을 출력한다.
그 다음 3 x 3 (n=3)일 때 i,j 좌표가 중앙일 때 공백을 출력한다.
n이 1이 되면 중단한다.
이렇게 n을 3으로 나누며 실행하는 재귀함수를 통해 원하는 별찍기 결과를 얻을 수 있다.
그런데 규칙은 어떻게 작성해야할까?
9x9 일 때(n=9), 중앙 공백 좌표는 3, 4, 5이다. 즉, (i/3) % 3이 1일 때이다.
따라서 9x9 크기에서 중앙 공백 좌표는 (i/3) % 3 == 1 && (j/3) % 3 == 1 로 표현할 수 있다.
3x3일 때는(n=3), 중앙 공백 좌표는 1, 4, 7이다. 즉, i % 3이 1일 때 이다.
따라서 3x3 크기에서 중앙 공백 좌표는 i % 3 == 1 && j % 3 == 1 로 표현할 수 있다.
재귀함수를 생각해 일반화된 규칙을 만들어야 하므로
(i/1) % 3 == 1 &&(j/1) % 3 == 1 의 규칙을 가진다고 표현할 수 있다.
이제 재귀함수를 통해 n이 3으로 나누어지면서 해당 규칙들을 만족시키게 작성해보면
크기 n에서 재귀함수를 통해 중앙 공백 좌표 규칙은
(i/(n/3)) % 3 == 1 && (j/(n/3)) % 3 == 1
이렇게 작성할 수 있다.
이렇게 되면 n이 9일 때, (i/3)
n이 3일 때, (i/1) 규칙을 만족시킨다. n이 그보다 높은 수일 때도 마찬가지이다.
일반화된 규칙을 찾은 것이다.
#include<iostream>
using namespace std;
void recur(int i, int j, int x) {
if (x == 1) {
cout << "*";
return;
}
else if ((i/(x/3)) % 3 == 1 && (j/(x/3)) % 3 == 1) {
cout << " ";
}
else {
recur(i, j, (x/3));
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
recur(i, j, n);
}
cout << "\n";
}
return 0;
}
'C++ 코딩테스트 공부 (중단) > c++ 백준 문제풀이' 카테고리의 다른 글
백준 c++ 17478번 문제 : 재귀함수가 뭔가요? (0) | 2022.05.21 |
---|---|
#8 기본수학2 - 2 (0) | 2022.04.06 |
#8 기본 수학2 - 1 (0) | 2022.04.05 |
#7 기본 수학1 - 2 (0) | 2022.04.04 |
#7 기본 수학1 - 1 (0) | 2022.04.01 |