[백준 2447번] 별 찍기 - 10

정환우·2021년 3월 22일

C 백준 분할 정복 알고리즘

백준

목록 보기

10/15

문제 링크

문제

해결

문제를 읽으면 느낌은 아마도 다 올 것이다. 아, 문제에서 주어진 N=3 일때의 모양 틀은 똑같고 크기만 커지는 거구나. 라고

솔직하게

근데 이걸 어떻게 코드로 짜느냐.....이게 문제다.

사실 나도 도저히 모르겠어서 다른 사람의 코드를 참조했다.

이 문제만 3번째 푸는 거 같은데.. 하...

차근차근 접근하기

우선 N=3 일때 모양을 보자. (캡처가 되지 않아서 문제에 있는 것을 보면)

왼쪽 위가 (0,0) , 오른쪽 아래가 (2,2)이라고 가정했을 때, 별이 빈 공간은 (1,1)의 좌표를 갖는다.

N=9 일 때를 보자.

마찬가지로 좌표를 설정했을 때, 첫 번째 N=3일 때를 확장해서, (1,4), (1,7) 부분도 비어있는 것을 알 수 있다.

즉, y % 3 == 1 && x % 3 == 1 일 때, 빈 공간이 출력된다는 것을 알 수 있다.

가운데에 비어있는 좌표는 (3,3) , (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5) 이다.

기본단위 모형이 한개가 나온 후에 비어있다는 뜻으로 해석이 된다.
즉, ((y/3) % 3) == 1 && ((x/3) % 3) == 1 을 만족하면 빈칸을 출력하면 되는 것이다.

즉 핵심적인 틀은,

y % 3 == 1 && x % 3 == 1 일 때, 빈칸을 출력한다.
((y/3) % 3) == 1 && ((x/3) % 3) == 1 일 때, 빈칸을 출력한다.

그런데, 2번식은 1번식에 x,y 대신 x/3, y/3를 넣은 식이다. 그리고 그리고, x/3, y/3 대신 N이 커질수록 다른 수도 넣어야 하므로, 매개 변수를 조작해서 설정해주면 된다는 것을 유추할 수 있다.

코드

#include <iostream>
using namespace std;

void start(int i, int j, int num){
if((i/num) % 3 == 1 && (j/num) % 3 == 1)
	cout << ' ';	// 아까 구한 조건식.
else{
	if(num / 3 == 0)	// num을 나눌 때 까지 나누다가 안나눠지면
    		cout << '*';
        else	
        	start(i,j,num/3);
    }
    
int main(){
int N;
cin >> N;
for (int i = 0; i<N; i++){
	for(int j = 0; j<N; j++)
    		star(i,j,N)
            }
        cout << '\n';
}