https://www.acmicpc.net/problem/10994
문제
> 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.
접근
예제를 보면 1일 때 별 하나가 찍혀있다.
2일 땐 1일때의 별 하나의 주위를 감싸는데 한 칸 띄고 둘러쌓고있다.
3일떄도 마찬가지로 1의 별을 한칸 띄고 둘러싸고, 그 걸 다시 한칸 띄고 둘러싸고있다. 4일때도 마찬가지이다.
즉, 입력받은 수는 총 별의 둘레 수 라고할 수 있다.
규칙 찾기
> 먼저 규칙을 구해준다. 입력받은 수에 따라 둘러지는 별이 다르다고 생각했지만 이를 1일 때 1,1크기의 사이즈의 별과, 이를 둘러싼 3,3크기의 공백을 한 쌍이라고 생각하고 규칙을 찾기 시작했다.
> 그럼 2일 때도 1,1과 3,3이 쌍이고, 5,5와 7,7이 쌍이다. 이런식으로 각 입력에 대해 겉에 안보이는 공백 또한 둘러싸고있다.
> 그러면 총 크기는, 1->3,3 2->7,7 3->11,11 4-> 15,15이다. 즉 이를 수식화하면 4*n-1이다. 따라서 최초의 크기는 4*n-1로 부울형 이차원 벡터를 선언한다.
> 이제 특정 인덱스를 범위로 잡아 그 인덱스에 값을 false, true로 주어 별을 찍을 곳을 정해야한다.
3일 때를 예로 들면, 0,0부터 10,10까지 전부 false로 주고
1,1부터 9,9까지 true로 주어별을 찍어야하고
2,2부터 8,8까지 false, 3,3부터 7,7 true, 4,4부터 6,6 false, 5,5 true 이런식으로 간다.
> 이를 위해 반복문의 범위를 수식화 해야한다. 시작지점은 0부터지만 벡터선언하며 0,0부터이미 false로 선언해서 1,1부터 시작한다.
> 1부터 시작하고 끝범위는 위에서 구한 쌍대로 나열해 규칙을 구해보면 true가 올때는 4*n-3번째이다.
근데 이제 이 값을 1씩 증가, 감소 시켜야 안으로 한칸씩 들어가며 별을 찍고 공백을 찍고를 하기 때문에 추가로 처리해줘야한다.
> 3일 때 보면 1~9, 2~8, 3~7, 4~6, 5 총 5번을 해줘야한다. 즉 이 횟수는 2*n-1번이다. 따라서 이 처리를 0부터 2n-1번 까지 해주며 각각의 처리에 t를 더해주고, 빼주면 t가 0부터 1씩 증가하므로 원하는 범위를 지정할 수 있다.
> 범위 지정이 끝났고 그럼 이제 찍어야할 반복때 벡터의 값을 반전시켜주어 false, true가 번갈아가며 나오도록 해준다. 출력을 해보면 제대로 나온다. 이제 이를 재귀화 해야한다.문제해결(재귀)
> 1. main함수는 입력으로 n을 받고 전역으로 선언한 이차원벡터를 assign으로 크기와 초기값을 설정해준다.
재귀에 사용할 Star함수에 위에서 구한 규칙에서의 t값, 반복문의 시작값, 끝값(4n-3)을 넣어시작한다.
위 함수가 끝나고 결과를 출력하기 위해 true로 찍힌 벡터값에 별을, false로 찍힌 곳에 공백을 찍는다. 제일 밖의 공백 테두리는 필요없으므로 1부터 반복문을 시작해 제외해준다.
> 2. 재귀의 탈출구는 규칙에서 특정 n에 대해 별을 찍을 곳의 처리의 총 횟수가 2n-1번으로 구했으므로 인자로 들어온 t의 값이 2n-1과 같다면 재귀를 끝내준다.
> 기능부분은 입력받은 r과 c로 반복문의 시작과 끝을 정의해주고 해당 값을 반전시켜준다.
반복문에서 반전이 끝나면 재귀를 해야한다. 이때 재귀에 값으로 1증가한 t, 1증가한 r, 1감소한 c를 넣어 재귀한다.
> 그러면 차례대로 t=0->1~9, t=1->2~8, t=2->3~7, t=3->4~6, t=4->5~5하고 t가 5로 새로 재귀로 넘어가는데 이때 탈출조건에 걸려 재귀가 깨진다.
차례대로 위 재귀들이 깨져 결국 첫Star함수 호출이 끝나고 main문의 별 출력문이 실행된다.
코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int n;
vector<vector<bool>> star;
void Star(int t, int r, int c)
{
if (t == 2 * n - 1) return;
else
{
for (int i = r; i <= c; i++)
{
for (int j = r; j <= c; j++)
{
star[i][j] = !star[i][j];
}
}
Star(t+1, r + 1, c - 1);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
star.assign(4 * n - 1, vector<bool>(4 * n - 1, false));
Star(0, 1, 4*n-3);
for (int i = 1; i < star.size() - 1; i++)
{
for (int j = 1; j < star.size() - 1; j++)
{
if (star[i][j] == true) cout << "*";
else cout << " ";
}
cout << '\n';
}
}
후기
규칙 찾는데만 2시간정도 노려봤다. 처음 각 n에 대해 벡터의 사이즈의 규칙을 먼저 늘어놓고 이를 수식화했다.
다음으로 주먹구구 식으로 어디 위치가 별이고 어디가 공백인지 다써보고 각각의 인덱스의 시작점과 끝점의 규칙을 찾았다. 그래서 각각 4n-1, 4n-3이런식이 나왔다.
이제 탈출 시기를 잡기위해 고민을 하던중, 별의 연산을하는 총 횟수를 또 n별로 늘어놓으니 2n-1이라는 규칙이 보였다. 이를 또 집어넣었다.
막상 해결하는건 쉬웠는데 이 규칙찾는게 진짜 극악이었다.
