2903번 중앙 이동 알고리즘, 2292번 벌집,1193 분수 찾기,2869 달팽이는 올라가고 싶다.

코딩테스트 : 2903번 중앙 이동 알고리즘

문제

상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다.

외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다.

알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.

1. 정사각형의 각 변의 중앙에 점을 하나 추가한다.
2. 정사각형의 중심에 점을 하나 추가한다.

초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다.

아래 그림은 과정을 총 2번 거쳤을 때까지의 모습이다.

초기 상태 - 점 4개	1번 - 점 9개	2번 - 25개

상근이는 어떤 점은 한 개 보다 많은 정사각형에 포함될 수 있다는 사실을 알았다. 메모리 소모량을 줄이기 위해서 중복하는 점을 한 번만 저장하려고 한다. 과정을 N번 거친 후 점 몇 개를 저장해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 15)

출력

첫째 줄에 과정을 N번 거친 후 점의 수를 출력한다

namespace ConsoleApp1
{
    public class Program
    {
        public static void Main()
        {
            int n = Int32.Parse(Console.ReadLine());
            int dot = 2;

            for (int i = 0; i < n; i++)
            {
                dot = (dot - 1) * 2 + 1;
            }
            Console.WriteLine(dot * dot);
        }
    }
}

 

코딩테스트 : 2292번 벌집

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

 

namespace ConsoleApp1
{
    public class Program
    {
        public static void Main()
        {
            int n = Int32.Parse(Console.ReadLine());

            int lineNumber = 1;
            int counter = 6;

            for (int i = 0; i < 15; i++)
            {
                if (n <= lineNumber)
                {
                    Console.WriteLine(i + 1);
                    break;
                }
                lineNumber += counter;
                counter += 6;
            }
        }
    }
}

 

범위를....15로...하고 왜 안되지... 한참 봤었다.

 

 

 

코딩테스트 : 1193 분수 찾기

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

namespace ConsoleApp1
{
    public class Program
    {
        public static void Main()
        {
            int n = int.Parse(Console.ReadLine());

            int lineNumber = 1;
            int counter = 2;
            

            for (int i = 0; i < Int32.MaxValue; i++)
            {
                if (n <= lineNumber)
                {
                    int diff = lineNumber - n;

                    int denominator = i + 1 - diff;
                    int numerator = diff + 1;

                    if (i % 2 != 0)
                    {
                        Console.WriteLine($"{denominator}/{numerator}") ;
                    }
                    else
                    {
                        Console.WriteLine($"{numerator}/{denominator}");
                    }
                    break;
                }
                lineNumber += counter;
                counter += 1;
            }
        }
    }
}

처음에 '지그재그로 읽는다'는 말 뜻을 잘 이해하지 못해서 잉 맞는 것 같은데 왜 안되는거지 ! 했다가 여러 예시들을 집어넣고나서 조건식을 달았다. 문제좀 제대로 읽자

다른 사람의 흥미로운 풀이

무려 140자 정도만에 푸신 분이 있는데 논리는 똑같다. 

 

코딩테스트 : 2869 달팽이는 올라가고 싶다.

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

public class Program
{
    public static void Main()
    {
        string[] numbers = Console.ReadLine().Split(' ');
        
        int[] numberArray = Array.ConvertAll(numbers, int.Parse);
        
        
        int up = numberArray[0];
        int down = numberArray[1];
        int goal = numberArray[2];
        int current = 0;
        int day = 1;

        while (true)
        {
            current += up;
            if (current >= goal)
            {
                Console.WriteLine(day);
                break;
            }
            else
            {
                current -= down;
            }
            day++;
        }
    }
}

 

처음에 이렇게 풀었더니, 처음으로 '시간 초과'가 나왔다. 보니까 문제의 숫자 범위가 상당히 넓고, 시간 제한이 0.25초였다.

그래서 하나하나 더해주면서 풀 생각 말고, 나눗셈으로 한 번에 풀 수 있는 방법을 생각해봤다. 

public class Program
{
    public static void Main()
    {
        string[] numbers = Console.ReadLine().Split(' ');
        
        int[] numberArray = Array.ConvertAll(numbers, int.Parse);
        
        
        int up = numberArray[0];
        int down = numberArray[1];
        int goal = numberArray[2] - up;
        int upbyday = up - down;

        if (goal % upbyday != 0)
        {
            Console.WriteLine(goal/upbyday + 2);
        }
        else
        {
            Console.WriteLine(goal/upbyday + 1);
        }

       
    }
}

 

도달 목표에서 하루에 올라갈 수 있는 길이를 빼 준다. 그럼 달팽이가 그 길이까지는 중간에 넘어도, 밤에 다시 내려가게 되는 일을 반복하게 된다. 그리고 그 길이까지 도달하는 날짜를 구해주면 된다. 

 

다른 사람의 흥미로운 풀이

 

굳이 day + 1  +2 를 나눠줄 필요가 없을 것 같기도 하다.