1074번 z

https://www.acmicpc.net/problem/1074

1074번: Z

재귀함수를 사용해서 풀으라했는데 호출한 함수가 자신의 함수를 또 호출하는 반복 함수가 재귀함수라 한다

그래서 일정 조건을 안걸어주면 스택 오버플로우가 발생한다 함 꼭 탈출조건을 걸어줘야한다

Math.Pow(double x, double y)를 사용하면 지정된 숫자의 거듭제곱을 반환해준다 double로 반환하기때문에

int로 바꿔줘야 함!!

함수를 만들어서 size, row, col 같이 넣어주고

이차원 배열이니까 사이즈가 2 인가?

2가 아니면 반으로 나눠서 2차원배열이 될 때까지 나누어야 함 

2이면 row, col 확인해서 맞는지 보고 맞으면 카운트 출력

안맞으면 row, col 번갈아가면서 size/2 더하고 또 안맞으면 양쪽다 넣어준다

이렇게 차근차근 계산해가면 정답이 나온다

근데 정확히 어떻게 어느부분이 계산이 되고 돌아가는지 잘 모르겠다

 

 

설명을 다시 들었다 함수를 호출하는 건 좋은데 다 도는 것은 안좋고

일정 걸음수?를 알수있으니까 다 돌지말고 일정부분 지나간 것을 계산 할 수있으니

마지막 구역만 돌고 그 걸음수를 더해서 마지막 구역만 돌게끔 만들어야한다

 

다시 풀어보자

size, row, col 주어지니까 size 보고 r, c 봐서 사이즈에 맞게 얼만큼 갔는지 봐서 따로 계산하고

마지막 구역 알아내서 돌고 그 숫자에 위에 계산한 숫자를 더해서 출력해야 한다.

 

 

using System;

namespace _1074
{
    class Program
    {
        static int N;
        static int row;
        static int col;
        static int count;

        static void Main(string[] args)
        {

            var input = Console.ReadLine().Split(' ');
            N = (int) Math.Pow(2, int.Parse(input[0]));
            row = int.Parse(input[1]);
            col = int.Parse(input[2]);

            function(N, 0, 0);

        }

        public static void function(int size, int r, int c)
        {
            if (size == 2)
            {
                if (row == r && col == c)
                {
                    Console.WriteLine(count);
                    return;
                }
                count++;
                if(row == r && col == c + 1)
                {
                    Console.WriteLine(count);
                    return;
                }
                count++;
                if(row == r+1 && col == c)
                {
                    Console.WriteLine(count);
                    return;
                }
                count++;
                if(row == r+1 && col == c+1)
                {
                    Console.WriteLine(count);
                    return;
                }
                count++;
            }
            else
            {
                function(size / 2, r, c);
                function(size / 2, r, c+size/2);
                function(size / 2, r + size / 2, c );
                function(size / 2, r + size / 2, c + size / 2);
            }
        }
    }
}

 다 도는게 아니라 사분면 구역을 알아내서 걸음수를 계산해서 result에 담아놓고 마지막 돌고 계산해서 출력했다

size * size 해서 나누기 4해서 사분면 걸음수 알아내서 넣어주면 됨

using System;

namespace _1074
{
    class Program
    {
        static int N;
        static float row;
        static float col;
        static long result;

        static void Main(string[] args)
        { 
            var input = Console.ReadLine().Split(' ');
            N = (int)Math.Pow(2, int.Parse(input[0]));
            row = int.Parse(input[1]);
            col = int.Parse(input[2]);
            result = 0;
            function(N, row, col);
        }

        static void function(int size, float r, float c)
        {
            if (size / 2 == 1)
            {
                if(size / 2 > r && size / 2 > c)
                {
                    Console.WriteLine(result);
                }

                else if (size / 2 > r && size / 2 <= c)
                {
                    Console.WriteLine(result + 1);
                }
                else if (size / 2 <= r && size / 2 > c)
                {
                    Console.WriteLine(result + 2);
                }
                else if (size / 2 <= r && size / 2 <= c)
                {
                    Console.WriteLine(result + 3);
                }
            }
            else
            {
                if(size/2 > r && size/2 > c) //1사분면
                {
                    function(size / 2, r, c);
                }
                else if(size / 2 > r && size / 2 <= c) //2사분면
                {
                    result += size * size / 4;
                    function(size / 2, r, c - size / 2);
                }

                else if (size / 2 <= r && size / 2 > c) //3사분면
                {
                    result += (size * size / 4) * 2;
                    function(size / 2, r - size / 2, c);
                }

                else if (size / 2 <= r && size / 2 <= c) //4사분면
                {
                    result += (size * size / 4) * 3;
                    function(size / 2, r - size / 2, c - size / 2);
                }
            }
        }
    }
}