[BAEKJOON] 백준 7770: 아즈텍 피라미드 (C#)

문제 링크

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

 

 

문제

아즈텍의 황제 쿠이틀라우악은 자신의 명예를 위해 피라미드를 만들려고 한다.

아즈텍 피라미드는 돌 블록을 이용해서 만든다. 블록은 1×1×1 크기의 정육면체이다. 쿠이틀라우악은 피라미드의 설립식 때, 블록 하나를 직접 땅에 놓았다. 그 다음 블록부터는 인부들이 설치하며, 이전에 놓여진 블록과 적어도 한 면 전체를 공유해야 한다.

왼쪽 두 개는 가능한 블록의 배치, 오른쪽 세 개는 불가능한 배치이다.

블록은 땅의 바로 위에 있거나, 블록의 아래에 있는 블록의 모든 면이 땅이나 다른 블록과 접할 때, 안정적이라고 한다. 피라미드의 모든 블록은 안정적이어야 한다.

아래 그림은 회색 블록을 놓았을 때이며, 그 블록이 안정적인 경우는 왼쪽 세 개, 아닌 경우는 오른쪽 두 개이다.

사용할 수 있는 블록의 개수가 주어졌을 때, 그 블록으로 만들 수 있는 가장 높은 안정적인 피라미드의 높이를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 사용할 수 있는 블록의 수 n이 주어진다. (1 ≤ n ≤ 10^9)

 

 

출력

첫째 줄에 블록 n개로 만들 수 있는 가장 높은 안정적인 피라미드의 높이를 출력한다.

 

 

 

통과한 답안

namespace _7770
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int cnt = 0;
            long total = 0;

            for (int i = 1; ; i++)
            {
                long now = 2 * i * i - 2 * i + 1;

                if (total + now > N)
                {
                    break;
                }

                total += now;
                cnt++;
            }

            Console.WriteLine(cnt);
        }
    }
}

 

주어진 1 x 1 x 1 크기의 정육면체 N개로 아즈텍 피라미드를 만들 때,

안정적인 아즈텍 피라미드는 이전에 놓여진 블록과 적어도 한 면을 공유해야 된다는 조건이 있다.

이 조건을 만족하는 가장 높은 안정적인 피라미드의 높이를 구하는 문제이다.

 

우선 각각의 안정적인 피라미드에 들어가는 최소 정육면체의 개수를 찾아보면,

1층은 1개, 2층은 5개, 3층은 13개, 4층은 25개, 5층은 41개, ... 이 필요하다.

각 층마다 필요한 정육면체의 개수는 4 * n개씩 늘어나므로,

a(n) - a(n-1) = 4(n - 1) 이다.

이를 이용하여 일반항을 구하면,

위와 같이 구할 수 있다.

 

이를 이용해서 코드를 작성하면,

0층부터 시작해서 1층씩 필요한 정육면체를 뺀다고 했을 때,

1층에 1개, 2층에 5개, 3층에 13개, ... 을 사용하는데

총 사용한 정육면체의 개수가 N개를 넘어가는 시점에 for 문을 종료하도록하여

주어진 N개의 정육면체로 만들 수 있는 가장 높은 안정적인 피라미드의 높이를 구할 수 있다.