2447번 별 찍기 -10, 11792번 하노이 탑 이동 순서

코딩테스트 : 2447번 별 찍기 - 10  

문제
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***
N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력
첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력
첫째 줄부터 N번째 줄까지 별을 출력한다.

using System.Data;
using System.Text;

public class BaekJoon
{
    public static void Main()
    {
       int n = Convert.ToInt32(Console.ReadLine());
       
       int[,] stars = new int[n, n];
       for (int i = 0; i < n; i++)
       {
           for (int j = 0; j < n; j++)
           {
               stars[i, j] = 1;
           }
       }
       DeletStarts(stars,0,0,n);
       
       StringBuilder sb = new StringBuilder();
       for (int i = 0; i < n; i++)
       {
           for (int j = 0; j < n; j++)
           {
               if (stars[i, j] == 1) sb.Append('*');
               else sb.Append(' ');
           }
           sb.AppendLine();
       }
       Console.WriteLine(sb);
    }

    public static void DeletStarts(int[,] stars, int row, int col, int n)
    {
        if (n < 2) return;
        
        int onesquare = n / 3;

        for (int i = row + onesquare; i < row + onesquare * 2; i++)
        {
            for (int j = col + onesquare; j < col + onesquare * 2; j++)
            {
                stars[i, j] = 0;
            }
        }

        for (int i = row; i < row + n; i += onesquare)
        {
            for (int j = col; j < col + n; j += onesquare)
            {
                DeletStarts(stars,row,col,onesquare);
            }
        }
    }
}

흠... 이런 식으로 반복문 돌면서 하는 건 안되나 ? 라고 생각했다

결국 가장 큰 곳에서부터 지워야, 오류 없이 지워질 것 같아서 큰 곳에서부터 반복 실행했다. 

그런데 결과가.. 

 

보니까 가장 첫 번째 반복만 실행되는 오류가 있었다.

 

++ 난 멍청하다. i j로 안바꿔 주었다. 

using System.Data;
using System.Text;

public class BaekJoon
{
    public static void Main()
    {
       int n = Convert.ToInt32(Console.ReadLine());
       
       int[,] stars = new int[n, n];
       for (int i = 0; i < n; i++)
       {
           for (int j = 0; j < n; j++)
           {
               stars[i, j] = 1;
           }
       }
       DeletStarts(stars,0,0,n);
       
       StringBuilder sb = new StringBuilder();
       for (int i = 0; i < n; i++)
       {
           for (int j = 0; j < n; j++)
           {
               if (stars[i, j] == 1) sb.Append('*');
               else sb.Append(' ');
           }
           sb.AppendLine();
       }
       Console.WriteLine(sb);
    }

    public static void DeletStarts(int[,] stars, int row, int col, int n)
    {
        if (n < 2) return;
        
        int onesquare = n / 3;

        for (int i = row + onesquare; i < row + onesquare * 2; i++)
        {
            for (int j = col + onesquare; j < col + onesquare * 2; j++)
            {
                stars[i, j] = 0;
            }
        }

        for (int i = row; i < row + n; i += onesquare)
        {
            for (int j = col; j < col + n; j += onesquare)
            {
                DeletStarts(stars,i,j,onesquare);
            }
        }
    }
}

다른 사람의 흥미로운 풀이

 

하나씩 쌓아가면서 푸신 분들이 계신데 사실 잘 이해가 가진 않는다. 

 

 

코딩테스트 : 11792번  하노이 탑 이동 순서   

문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.



입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력
첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

using System.Text;
using Microsoft.Win32.SafeHandles;

public class BaekJoon
{
    static void Main()
    {
        int input = Convert.ToInt32(Console.ReadLine());
        StringBuilder sb = new StringBuilder();
        int n = Hanoi(input, 1, 2, 3, 0,sb);
        Console.WriteLine(n);
        Console.WriteLine(sb);
    }
    public static int Hanoi(int n, int from, int bridge, int to, int count ,StringBuilder sb)
    {
        if (n == 0) return 0;

        if (n == 1)
        {
            sb.AppendLine($"{from} {to}");
            count++;
        }
        else
        {
            count = Hanoi(n - 1, from, to, bridge, count,sb);
            sb.AppendLine($"{from} {to}");
            count++;
            count = Hanoi(n - 1, bridge, from, to, count,sb);
        }

        return count;
    }
}

살짝 옛날에 했던거 쓰윽 보고 풀었다. 

연습장을 두 장쓰고 성공..! 

 

 

다른 사람의 흥미로운 풀이

 

하노이 탑의 총 반복 횟수( 원판을 옮기는 횟수) 가 2^n - 1 이라는 사실을 몰랐다. 

생각해보자면, 결국 끝에 옮기는 것은 1번이다. (가장 작은원반을 올릴 것이므로) 그리고 이 것을 바탕으로 , 

그 전의 행동이 두 번 반복되고 그 다음 가장 작은 원반을 옮기므로 + 1이 된다. 그러면 3번이 나온다. 또, 다음엔 3번 옮기는 것을 2번 반복하고 + 1이 된다. 그러면 7이 나온다. 이런 식으로 가다 보면 그 전 행동을 두 번 반복하고 + 1을 하는 것은 결국 2^n -1과 같게 된다. 
말을 좀... 이상하게 했지만 결국 그 전까지의 행동을 두 번 반복하고 한 개를 더 옮기는 것이다.

그런데 첫 번째 행동이 1 이므로 결국 1 3 7 15 31 .... 이 된다. 이 숫자들은 2^n -1과 같다..

 

 

---

근 3~4일동안 재귀 문제를 풀었다. 

결국 재귀라는 것이 자기 자신을 반복해서 호출해서 문제를 푸는것인데 

여기서 중요한 점은 끝나는 지점을 명확히 설정하는 것, 매개변수를 잘 설정하는 것, 작은 문제로 쪼개질 수 있는지 먼저 확인하는 것 인듯 하다. 

지금은 '재귀'라는 카테고리 안에 있어서 이걸 재귀식으로 풀어야지 ! 하고 생각했지만 다른 문제가 나오면 어찌될지 모른다. 반복문인지, 재귀인지 문제를 보고 알 수 있게 앞으로도 열심히 문제풀어야지...