2447번: 별 찍기 - 10
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이
www.acmicpc.net
본인이 해당 문제의 출제자가 아니며, 문제 자체에 대한 모든 사항은 위의 링크가 출처임을 명시합니다.
[백준/C++/Gold(5)] 2447 - 별 찍기 - 10
대체 뭘하면 흔한 별찍기 문제가 Gold 5씩이나 하는지 궁금해서 풀어보기로 했다.
문제 :
3이 입력일 경우,
*** * * ***
9가 입력일 경우,
********* * ** ** * ********* *** *** * * * * *** *** ********* * ** ** * *********
...
와 같은 재귀 문제이다.
(자세한 문제는 링크를 참조해주세요~ 완전히 베끼는 건 저작권에 문제가 있을 수 있으니...)
생각 :
일단 이미 문제를 읽어보면 "재귀"란 말이 적혀있는 것을 보면, 흔한 Divide And Conquer 문제인 듯해서 그대로 풀기를 시도했다.
처음에는 3^7이 얼마인지 모르겠어서 계산했는데...

그래서 그냥 통으로 map을 잡아둔 뒤에 거기에 있는 내용을 프린트하기로 했다.
코드 (성공):
#include <iostream> using namespace std; char map[2200][2200] = {0}; void recur(int n, int x, int y){ if(n != 3){ n /= 3; for(int a = 0; a < 3 * n; a += n){ for(int b = 0; b < 3 * n; b += n){ //cout << a << ':' << b << '\n'; if(a == n && b == n) { for(int c = x + a; c < x + a + n; c++){ for(int d = y + b; d < y + b + n; d++){ map[c][d] = ' '; } } } else { recur(n, x + a, y + b); } } } } else { for(int a = 0; a < 3; a++){ for(int b = 0; b < 3; b++){ if(a == 1 && b == 1) { map[x + a][y + b] = ' '; } else { map[x + a][y + b] = '*'; } } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; recur(n, 0, 0); for(int i = 0; i < n; i++){ cout << map[i] << '\n'; } return 0; }
바로 성공했다. 역시 그렇게 어렵지는 않았다.
recur 함수의 윗부분은 n>3 일 때 쓰는 함수이고, 이하의 재귀함수들과 중간에 비우는 공백을 출력하는 기능을 넣어두었다.
n=3의 경우에는 위와 같지만 좀 간소화된 함수를 넣어두었다. 위에만 있어도 되게 만들 수 있지만, 사실 n\eq3일 때의 기능을 먼저 만들고 본따서 위쪽의 기능을 만들었기 때문에 백업의 의미로써 남겨두었다.
확실히 dp문제에 비해서 D&Q가 훨씬 쉬운것 같다. dp는 silver 1인데 틀리고 gold 5인데 얘는 손쉽게 맞아버려서... 요즘 생각이 드는건데 그냥 어려운 알고리즘을 배우고 학습하는 것에 도전해서 더 어려운 문제를 푸는 것은 그렇게 나쁠 것 같지는 않다는 생각이다. 익숙해지면 좋으니까. 다음에는 아예 세그먼트 트리 / 레드 블랙 트리 / 다익스트라 같은 걸 다시 복습하는 건 어떤가 싶다.
'CP, PS > BeakJoon' 카테고리의 다른 글
[백준/C++/Platinum(5)] 14003 - 가장 긴 증가하는 부분 수열 5 (1) | 2023.09.03 |
---|---|
[백준/C++/Silver(1)] 2156 - 포도주 마시기 (0) | 2023.07.30 |
[백준/C++/Gold(5)] 28293 - 자릿수 구하기 (2) | 2023.07.25 |
[백준/C++/Gold(5)] 27087 - 직육면체 (2) | 2023.07.22 |
[백준/C++/Silver(3)] 1485 - 정사각형 (2) | 2023.07.22 |