[백준] 2448번 별 찍기 - 11
in Algorithms on BOJ
Divide & Conquer
문제설명
문제
예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.
입력
첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, …) (k ≤ 10)
출력
첫째 줄부터 N번째 줄까지 별을 출력한다.
접근
[백준] 2447번 쿼드트리 문제와 유사한 문제이다. 이번에는 사각형이 아닌 삼각형이라 많이 헷갈린다. mark라는 기본 형태를 따로 저장해두고 반복되는 세 삼각형마다의 기준점을 잡아서 재귀적으로 처리하였다. 기준점을 잡는 게 복잡해서 직접 그려보면서 확인할 수 있었다.
gongdoli 님의 블로그에 같은 방식에 대한 설명이 아주 자세히 나와있다. 참고하면 좋을 듯 하다.
코드
#include <iostream>
#define MAX_NUM 3100
using namespace std;
char stars[MAX_NUM][MAX_NUM*2];
char mark[][6] =
{
" * ",
" * * ",
"*****"
};
void star(int x, int y, int term){
if(term == 1){
for(int i =0; i<3; i++){
for(int j=0; j<5; j++){
stars[x+i][y+j] = mark[i][j];
}
}
}
else{
int new_term = term/2;
star(x , y + 3 * term / 2, new_term);
star(x + 3 * term / 2, y , new_term);
star(x + 3 * term / 2, y + 3 * term, new_term);
}
}
int main(){
int n;
cin >> n;
fill(&stars[0][0],&stars[MAX_NUM-1][MAX_NUM*2],' ');
star(1,1,n/3);
for(int i=1; i<=n; i++){
for(int j=1; j<=n*2; j++){
cout << stars[i][j];
}
cout << '\n';
}
}
참고
BOJ #2448
[백준] 2447번 쿼드트리
gongdoli님의 글
이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)
