[백준] 7770 - 아즈텍 피라미드

문제

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

아즈텍 피라미드는 1 * 1 * 1 크기의 정육면체 돌 블록으로 만든다. 피라미드는 먼저 블록 하나를 놓은 뒤, 이후에 놓는 블록은 이전에 놓인 블록과 한 면 전체를 공유해야 한다.

블록은 땅 바로 위에 있거나, 블록 아래에 있는 블록의 모든 면이 인접하고 있을 때 안정적이라고 하며, 모든 블록은 안정적이여야 한다.

사용할 수 있는 블록의 개수가 주어졌을 때, 블록으로 만들 수 있는 안정적인 피라미드의 높이를 구하여라.

 

 

풀이

계산하기 편하게 이미 쌓은 블록을 위로 올리고, 바닥에 놓아야 할 블록의 수를 생각해보자.

층에 따라 바닥에 최소로 놓아야 하는 블록의 수는 다음과 같다.

N층일 때 바닥에 놓아야 하는 최소 블록의 수를 구했다면, 전체 피라미드의 블록의 수는 N층까지의 바닥 블록 수의 합이라고 할 수 있다.

이제 코드로 구현해 보자.

 

 

구현

정해진 최대 층 수가 없으므로, 반복 조건은 전체 피라미드의 블록 수가 입력받은 피라미드의 블록 수보다 많아질 때까지 반복하도록 한다.

import sys

# 입력받은 블록 수
n = int(sys.stdin.readline())

# 바닥 블록 수. 초기값 1
bottoms = [1]

# 바닥 블록 수의 합이 입력 블록 수보다 많아질 때까지 반복
while n >= sum(bottoms):
    # N층일 때의 바닥 블록 수 계산
    bottoms.append(4 * len(bottoms) + bottoms[-1])

# 층 수 출력
print(len(bottoms) - 1)

 

 

참고 문서

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

https://comain.tistory.com/144