[2447] 백준 : 별 찍기 - 10(C++)
개인적으로 여태 푼 문제중 가장 이해가 안 되고 가장 오래고민했으나 결국 못 풀고 구글링해서 푼 문제다..ㅠㅠ
* 접근 방법
- 분할정복 알고리즘을 이용하자!
▶ 분할 정복 알고리즘?
- 주어진 문제를 작은 문제로 나누고(Divide) 각각의 작은 문제를 해결(Conquer)하는 것
1. 문제를 하나 이상의 작은 문제로 분할
2. 작은 문제들의 해답을 각각 구함(재귀함수 이용)
3. 작은 문제의 답을 통합하여 원래의 문제의 답을 구함
* 문제 분석
1) n=3인 경우
└ 별이 ㅁ 모양으로 반복
2) n=9인 경우
└ n=3인 경우가 ㅁ모양으로 반복
3) n=27인 경우
└ n=9인 경우가 ㅁ모양으로 반복
즉,
1. 입력한 숫자n(가로, 세로)을 3으로 나누어 9개로 분할
2. 정중앙의 큰 빈칸을 제외하고 나머지 칸은 재귀함수로 처리
* 풀이
- 공백의 좌표 : (1, 1), (1, 4), (1, 7), (1, 10), (1, 13), (1, 16), (1, 19), · · ·
- : (4, 1), (4, 4), (4, 7), (4, 10), (4, 13), (4, 16), (4, 19), · · ·
☞ ( x % 3 ==1 ) && ( y % 3 ==1 )
- 공백의 좌표 : (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)
= ( (x / 3) % 3 ==1 ) && ( (y / 3) % 3 ==1 )
- ㄴㄴㄴㄴ : (9, 9), (9, 10), · · ·, (9, 17), (10, 9), · · ·, (10, 17), · · ·, (17, 17)
= ( (x / 9) % 3 ==1 ) && ( (y / 9) % 3 ==1 )
☞ ( (x / n) % 3 ==1 ) && ( (y / n) % 3 ==1 )
- 두 규칙
( x % 3 ==1 ) && ( y % 3 ==1 )
( (x / n) % 3 ==1 ) && ( (y / n) % 3 ==1 ) 은 n=1인 경우에 같아짐
즉, 공백을 출력하는 조건은 다음과 같음
if ((x / n) % 3 == 1 && (y / n) % 3 == 1) {
cout << ' ';
}단 위의 조건은 n=1일때 같아지는 것이기 때문에
이는 재귀함수로 계속 n / 3을 해주고, 재귀함수의 종료조건은 n=1이 되는 순간인 n / 3 == 0
n=1이지만, 공백 조건에 해당하지 않은 경우는
공백 자리가 아니므로 ★을 출력!!
#include <iostream>
using namespace std;
void star(int x, int y, int n)
{
if ((x / n) % 3 == 1 && (y / n) % 3 == 1) {
cout << ' ';
}
else
{
if (n / 3 == 0)
cout << '*';
else
star(x, y, n / 3);
}
}
int main() {
int n;
cin >> n;
for (int x = 0; x < n; x++)
{
for (int y = 0; y < n; y++)
star(x, y, n);
cout << '\n';
}
}
다시 말하지만, 정말 나에겐 너무 힘든 문제였다.
처음엔 분할 정복이 뭔지도 몰랐지만, 분할 정복을 검색 한 이후에도 9개로 나누는 건 알겠는데 그 다음은??? 이랬었다..
첫 날은 3시간 정도 고민하다가 도저히 안되겠어서 다음날인 오늘 다시 풀어봤는데도
알 것 같으면서 모르겠는 문제..ㅜㅜ
구글링해서 코드를 봤는데, 조건이 왜 이렇게 된 건지 파악하는게 힘들어서 결국 총 10시간은 걸린것 같다ㅋㅋ
앞으로 이것처럼 이해 안 가고 모르는 문제가있으면, 이렇게 시간을 미련하게 끄는 것이 아니라..
적당히 답을 찾아 보는 것이 더 효율적일 것 같다..ㅠ