백준[2447/C#] 별 찍기 - 10

별찍기 너무 싫다... 

이번 별찍기 문제는 분할 정복을 이용하면 좋습니다.

일련의 규칙을 통해서 작게 작게 그려지는 사각형들로 큰 사각형을 이루고 있기 때문에

단위별로 분리해서 생각하고 큰문제로 적용시키면 좋겠지요.

 

1차적으로 분할해서 풀어본다면

 

	public void StarMain()
        {
            int num = int.Parse(Console.ReadLine());
            

            for(int i = 0; i < num; i++)
            {
                for(int j = 0; j < num; j++)
                {
                    if ((i % 3 == 1) && (j % 3 == 1))
                    {
                        Console.Write(" ");
                        continue;
                    }

                    Console.Write("*");
                }
                Console.WriteLine();
            }
        }

이렇게 풀어봤는데 이렇게 풀경우 3을 입력시엔 원하는대로 나오지만 3의n승의 값들은 원하는 대로 나오질 않게됩니다.

작은 사각형에도 가운데가 뻥뚫려야하고 큰 사각형에서도 뻥뚫려야하는데 큰사각형은 무시하고 똑같이 작은 사각형에서 뻥뚫린애들이 반복되게 됩니다.

 

어떻게 이문제를 해결해야할까요?

 

곰곰히 규칙을 생각해본결과...

3의 n승으로 커지고 있고 가운데 영역은 빈칸으로 둬야합니다.

그런데 3으로만 나누면 영역이 커지면 커질 수록 대응을 못하게 되겠지요.

그래서 

int dx = i / (num /3);
int dy = j / (num /3);

 

즉 크기의 3등분하여 가운데 영역을 빈칸으로 채우기로 했습니다.

9의 경우 가운데 3x3 영역이 비어있을테고 27의 경우 가운데 9x9영역이 비어있겠지요

즉 크기 나누기 3을 할경우 가운데 영역을 특정할 수 있고 이 값을 기준으로 나누면 되겠다고 생각했습니다.

적용하게되면 

27일 경우 3을 나눈 몫이 9일때 한번 체크를 하고 또다시 3으로 나눠서 3일때 체크 ! 그리고 또나눠서 1일때 체크

 

즉 27일때 9 3 1

9 일땐 3 1

이런식으로 체크해서 나머지가 1이면 빈칸으로 그려내어주면 되겠습니다.

 

	public void StarMain()
        {
            //크기를 결정하는 값
            int num = int.Parse(Console.ReadLine());
            

            for(int i = 0; i < num; i++)
            {
                for(int j = 0; j < num; j++)
                {
                    //빈칸인지 판별
                    if (IsEmptyDraw(i,j))
                    {
                        Console.Write(" ");
                        continue;
                    }

                    Console.Write("*");
                }
                //줄넘김
                Console.WriteLine();
            }
        }

        bool IsEmptyDraw(int dx, int dy)
        {
            //dx 즉 몫이 0인가?
            //3으로 나눈 몫들을 가지고 3으로 나누었을때 나머지가 1인지 판별하기 위해서
            while(dx != 0)
            {
                if (dx % 3 == 1 && dy % 3 == 1)
                    return true;

                dx /= 3;
                dy /= 3;
            }
            return false;
        }

즉 코드는 이렇게 되는데요.

 

문제는 콘솔창에 잘 뜨는거 같은데 테스트에 제출하게되면 시간 초과를 경험하게 됩니다.

갠적으로 띠용... 왜지?? 그랬는데

 

바로 console.writeline(); 을 하면 안되고, 스트링빌더를 만들어서 다 담아주고 마지막에 tostring()을 합시다.

 

그랬더니 겨우 맞았습니다!! 가 뜨네요.

 

	public void StarMain()
        {
            //크기를 결정하는 값
            int num = int.Parse(Console.ReadLine());
            StringBuilder sb = new StringBuilder();
            sb.Clear();
            

            for(int i = 0; i < num; i++)
            {
                for(int j = 0; j < num; j++)
                {
                    //빈칸인지 판별
                    if (IsEmptyDraw(i,j))
                    {
                        sb.Append(" ");
                        continue;
                    }

                    sb.Append("*");
                }
                //줄넘김
                sb.AppendLine();
            }

            Console.WriteLine(sb.ToString());
        }

        bool IsEmptyDraw(int dx, int dy)
        {
            //dx 즉 몫이 0인가?
            //3으로 나눈 몫들을 가지고 3으로 나누었을때 나머지가 1인지 판별하기 위해서
            while(dx != 0)
            {
                if (dx % 3 == 1 && dy % 3 == 1)
                    return true;

                dx /= 3;
                dy /= 3;
            }
            return false;
        }

StringBuilder를 사용하실때 using System.Text 잊지마시기바랍니다. 저도 한번 잊었다가 실패 띄웠네요.