반응형
https://www.acmicpc.net/problem/2447
💡 별 찍기 -10
✅ 문제 풀이
- 프렉탈 도형 문제
- 재귀함수를 사용한 분할과 정복으로 해결할 수 있다
- 도형의 패턴을 분석해보자.
위는 N=3일때의 도형의 출력 형태이다. 좌표로 따졌을 때 (1,1)만 비어있음을 알 수 있다.
위는 N=9일때의 도형의 출력 형태이다. 좌표로 따졌을 때 (1,1),(1,4),(1,7),(3,3),(3,4),(3,5),(4,1),(4,3),(4,4),(4,5),(4,7),(5,3),(5,4),(5,5),(7,1),(7,4),(7,7)이 비어있음을 알 수 있다.
좌표를 보니, (i/3)%3==1 과 (j/3)%3==1을 만족하는 경우에 비어있음을 확인할 수 있다.
또한 3*3 개별 도형들의 빈 자리는 (i/1)%3==1 과 (j/1)%3==1을 만족하는 경우에 비어있음을 확인할 수 있다.
따라서 중간에 나누어 지는 값은 3*3 도형이 한 변에 만들어지는 개수로 생각할 수 있고, 이는 n을 3으로 나누어가며 위의 공식에 만족할 경우 " "를, 그렇지 않으면 *을 출력하도록 하면 된다.
즉, *이 출력되는 경우는 위의 공식을 만족하지 않는 위치일 경우, 별을 하나 출력한다고 생각하면 되고, 그때마다 3*3 하나를 기준으로 하므로 num은 1이 될 것이다.
✏ 코드 전문
#include<iostream>
using namespace std;
void star(int i, int j, int num) {
if ((i / num) % 3 == 1 && (j / num) % 3 == 1) {
cout << " ";
}
else {
if (num / 3 == 0) {
cout << "*";
}
else {
star(i, j, num / 3);
}
}
}
int main() {
ios_base::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++) {
star(i, j, n);
}
cout << "\n";
}
return 0;
}
반응형
'CO-TE > 백준' 카테고리의 다른 글
[백준] 7569번 C++ "토마토" 풀이 / bfs, 3차원 벡터 (1) | 2024.01.29 |
---|---|
[백준] 10026번 C++ "적록색약" 풀이 / dfs, 너비 우선 탐색 (0) | 2024.01.27 |
[백준] 11729번 C++ "하노이 탑 이동 순서" 풀이 / 재귀호출 (1) | 2024.01.23 |
[백준] 7576번 C++ "토마토" 풀이 / BFS, 너비우선탐색 (1) | 2024.01.22 |
[백준] 12865번 C++ "평범한 배낭" 풀이 / DP, 동적계획법 (0) | 2024.01.12 |