mojo's Blog
[백준 10993] 별 찍기 - 18 본문
문제 링크 : 10993번: 별 찍기 - 18 (acmicpc.net)
문제
예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.
입력
첫째 줄에 N(1 ≤ N ≤ 10)이 주어진다.
출력
첫째 줄부터 차례대로 별을 출력한다.
예제 입력 1 복사
1
예제 출력 1 복사
*
예제 입력 2 복사
2
예제 출력 2 복사
*****
***
*
예제 입력 3 복사
3
예제 출력 3 복사
*
* *
* *
*******
* *** *
* * *
*************
예제 입력 4 복사
4
예제 출력 4 복사
*****************************
* * *
* * * *
* * * *
* ******* *
* * *** * *
* * * * *
***************
* *
* *
* *
* *
* *
* *
*
재귀를 활용한 별 찍기 문제이다.
접근 방식은 다음과 같다.
1. 먼저 규칙성을 따져보도록 하자.
N이 짝수일때와 홀수일때로 구분할 수 있다.
(1) N이 짝수일 경우 : 정삼각형이 180도 회전된 상태
(2) N이 홀수일 경우 : 정삼각형 그대로의 상태
2. N에 해당하는 정삼각형 내부에 N - 1에 해당하는 정삼각형이 존재하는 것을 알 수 있다.
좀 더 일반화해서 생각하면 다음과 같이 생각할 수 있겠다.
3. 2번 방법을 좀 더 구체적으로 생각해보도록 하자.
여기서 별을 찍기 위해서 2차원 좌표로 생각해보도록 해보자.
기준점을 빨간색 점 (x, y) 로 하여 (x, y) 를 기준으로 n 에 대한 별을 채우고 n - 1 에 대한 별을 채우고 n - 2 에 대한 별을 채우는 방식임을 알 수 있다.
즉, 재귀적으로 n과 기준점 (x, y) 를 가지고 n이 짝수인지 홀수인지에 대한 구분만 할 수 있다면 별을 채울 수 있다는 것이 핵심이다.
그렇다면 별을 채우기 위해서 2차원 배열 char 형 Star 이 필요할 것이고 위에서 설명한 방식 그대로 별들을 채워가면 된다.
※ 주의 사항
N = 0 이 되는 순간 재귀적 호출이 중지되도록 리턴하는 것을 잊지 말자.
그리고 별의 가장 오른쪽 부분은 ' ' 빈칸으로 채워진 것이 아니기 때문에 이에 대한 처리를 꼭 해주도록 해야 한다.
즉, 별 가장 오른쪽 다음을 ' ' 프린트를 하는 것이 아니라 개행 처리를 해줘야 한다.
Solution Code
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <math.h>
#define INF 1000000000
#define endl '\n'
#define ll long long
using namespace std;
char Star[2100][2100];
void init_Star(int N) {
int row = pow(2, N) - 1;
int col = row * 2 - 1;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
Star[i][j] = ' ';
}
}
}
void set_Star(int N_, int N, int x, int y) {
if (N == 0)
return;
if (N % 2 == 0) {
int gap = pow(2, N) - 1;
for (int i = 0; i < gap; i++) {
if (i == 0) {
for (int j = 0; j < 2 * gap - 1; j++)
Star[x + i][y + j] = '*';
}
else {
Star[x + i][y + i] = Star[x + i][y + (2 * gap - 2 - i)] = '*';
if (N_ == N) Star[x + i][y + (2 * gap - 1 - i)] = 'x';
}
}
set_Star(N_, N - 1, x + 1, y + pow(2, N - 1));
}
else {
int gap = pow(2, N) - 1;
for (int i = 0; i < gap; i++) {
if (i == gap - 1) {
for (int j = 0; j < 2 * gap - 1; j++) {
Star[x + i][y + j] = '*';
}
}
else {
Star[x + i][y + (gap - 1 - i)] = Star[x + i][y + (gap - 1 + i)] = '*';
if (N_ == N) Star[x + i][y + (gap + i)] = 'x';
}
}
set_Star(N_, N - 1, x + pow(2, N - 1) - 1, y + pow(2, N - 1));
}
}
void show_Star(int N) {
int row = pow(2, N) - 1;
int col = row * 2 - 1;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (Star[i][j] == 'x') break;
printf("%c", Star[i][j]);
}
printf("\n");
}
}
void solution() {
int N;
scanf("%d", &N);
init_Star(N);
set_Star(N, N, 0, 0);
show_Star(N);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solution();
return 0;
}
'백준 > etc' 카테고리의 다른 글
[백준 17136] 색종이 붙이기 (0) | 2022.02.04 |
---|---|
[백준 16991] 외판원 순회 3 (0) | 2022.01.26 |
[백준 2211] 네트워크 복구 (0) | 2021.12.30 |
[백준 5052] 전화번호 목록 (0) | 2021.11.08 |
[백준 9527] 1의 개수 세기 (0) | 2021.11.07 |