[백준] 2097 조약돌 (Baekjoon Problem 2097: Pebbles)

문제 출처

 

[문제 요약]

N (1 <= n <= 500,000,000)개의 조약돌이 모눈종이 위에 펼쳐질때 (모눈종이의 교차점에 놓여짐)

최소 둘레를 구하라

 

예시들이 있는데 이를 그림으로 그려보면

5
6

예시 1

14
12

예시 2

[풀이]

둘레가 최소가 되게 하려면 너비와 높이가 최대한 비슷해야한다.

그래서 조약돌의 개수 < 어떤수 n의 제곱이 되는 시점을 찾아준다.

 

[유의할 점 #1]

단순히 제곱만 볼게 아니라

n-1 * n보다 조약돌의 개수가 많은지도 확인을 해야한다.

예시 1에서 5는 2^2 보다 크고 3^2보다는 작지만

추가적으로 2*3보다 큰지 확인했을때 작으므로 가로 혹은 세로 한변이 더 작다.

 

[유의할 점 #2]

둘레는 각 꼭짓점도 포함하기 때문에 (둘레에 들어가는 조약돌 수 -1) 을 하고 곱해주어야한다.

예시 2 에서 한변에 들어가는 조약돌 수는 4개이지만 너비와 높이는 3이며 둘레는 3*4 = 12임을 유의한다.

 

[유의할 점 #3]

여기서 사각형이 만들어져야 둘레가 나오므로 1줄로 나열은 불가하다.

조약돌이 하나일때는 따라서 둘레가 0이 아닌 4 (=1*4) 가 되어야 한다.

이 경우를 따로 다루어주어야 한다

 

[파이썬 3 코드]

적고 나서 느끼는건데 square_range에서 각각 변에 들어가는 조약돌 개수를 돌려주고 min_circum은 이름을 circum (circumference)로 바꿔서 둘레만 구하는걸로 짰으면 더 직관적이었을거 같다.

def square_range(pebbles):
    i = 0
    while pow(i, 2) < pebbles:
        i += 1
    return i

def min_circum(num, pebbles):
    if (num-1) * num > pebbles:
        return (num-2 + num-1) * 2
    else:
        return (num-1) * 4

if __name__ == "__main__":
    pebbles = int(input())

    # 1은 0 <- 아니지! 2는 4가 맞긴함
    if pebbles == 0: # 핸들 해줄필요 없긴함
        print(0)
    elif pebbles == 1:
        print(4)
    else:
        sq_num = square_range(pebbles)
        circumference = min_circum(sq_num, pebbles)
        print(circumference)