BOJ 2447번 별 찍기 - 10

BOJ : https://www.acmicpc.net/problem/2447

GitHub : https://github.com/junho0956/Algorithm/blob/master/2447/2447/%EC%86%8C%EC%8A%A4.cpp

 

별찍기 튜토리얼중에 가장 어려웠던 것 같다.

그만큼 별찍기 문제중 유명한 문제이기도 하다.

 

힌트는 3의 제곱수라는 것과, 공백 좌표를 유심히 봐야하는 것이다.

옆의 사진에서 보면 n = 9 기준에서 공백이 되는 좌표는

(1,1) (1,4) (1,7) (4,1) ...

그리고 정중앙에 텅비게되는 (3,3) (3,4) (3,5) ...

 

이 숫자들을 싹다 3으로 나누어본다.

3으로 나누어보면서 알게되는 규칙은

현재 좌표 dx, dy 를 3으로 나눈 나머지가 둘다 1인 경우

그 지점은 공백이 되는 지점이라는 것이다.

어느 한 좌표라도 나머지가 1이 아니라면 그곳은 * 이 되는 지점이다.

 

이를 이용하여 코드를 구현하였다.

 

#include <iostream>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
 
    int N; cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            int dx = i, dy = k;
            while (1) {
                if (dx == 0 || dy == 0) break;
                if (dx % 3 == 1 && dy % 3 == 1) break;
                dy /= 3, dx /= 3;
            }
            if (dx && dy) cout << " ";
            else cout << "*";
        }
        cout << "\n";
    }
    return 0;
}