백준 14606번 피자 (Small) - 파이썬(Python)

백준 14606번

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

 

정답코드1) 시간: 72ms

- 답은 맞았지만 비효율적이었던 나의 첫 번째 풀이.

- 즐거움의 총합은 N을 반으로 나누었을 때가 가장 크다. N을 반으로 나누는 과정을 모든 피자탑이 1층이 될 때까지 반복하며 즐거움 값을 더한다. N의 값이 홀수, 짝수일 때로 나누어 계산한다.

N = int(input())
result = 0

def devide(N):
    global result
    if(N == 1): return
    if N % 2 == 0: #짝수 개
        n1 = N / 2
        n2 = N / 2
        result += n1 * n2
        devide(n1)
        devide(n2)
    else: #홀수 개
        n1 = int(N / 2)
        n2 = N - n1
        result += n1 * n2
        devide(n1)
        devide(n2)

devide(N)
print(int(result))

 

정답코드2) 시간: 68ms

- 알고리즘: 다이나믹 프로그래밍 (큰 문제를 여러 작은 문제로 나누어 푸는 기법, 반복되는 계산은 저장해서 재사용함)

- 첫 번째 풀이와 다른 점:

① N을 1까지 쪼개는 방향이 아니라, 반대로 1부터 쌓아올리는 방향으로 계산한다. 이렇게 하면 전 단계에서의 즐거움 값을 저장해두었다가 재사용할 수 있다.

② N을 홀수, 짝수로 나누어 계산할 필요 없이 몫(i//2)을 계산하는 것으로 바꾸었다. 

N = int(input())
floor = [0] * 11 #N의 개수에 따른 즐거움의 값을 저장

#점화식을 적용할 수 없는 값은 미리 계산
floor[1] = 0 #N=1이면 즐거움은 0
floor[2] = 1 #N=2이면 즐거움은 1

#N=3부터 현재 개수까지 순차적으로 즐거움 값을 계산
for i in range(3, N+1):
    k = i//2 #N을 반으로 나눈 값
    floor[i] = k * (i-k) + floor[k] + floor[i-k] #즐거움값 + 절반1 + 절반2    
print(floor[N])

 

정답코드3) 시간: 68 ms

- 알고리즘: 수학

- 결과를 잘 살펴보자. N=2, 3, 4, 5일때 즐거움=1, 3, 6, 10임을 발견할 수 있다. 즉 이를 N * (N-1) / 2로 표현하여 간단하게 계산할 수도 있다.

N = int(input())
print(N * (N-1) // 2) #정수로 출력하기 위해 //사용

 

문제

갑은 아주대학교 학생입니다. 갑은 팔달관 1층에서 학과 개강총회를 준비하고 있습니다. 갑은 피자를 N 판 시켰습니다. 식탁 위에 피자 N 판이 탑처럼 쌓여있습니다. 갑은 높이가 N 인 이 한 피자탑을, 높이가 1인 피자탑들로 분리시켜야 합니다. 갑은 혼자 놀기를 하며 즐겁게 일을 해결하기로 합니다. 그래서 다음과 같은 놀이를 하기로 했습니다.

먼저 놀이를 시작하기 전에, 식탁 위엔 N 개의 피자판이 하나의 탑으로 쌓여있습니다. 놀이가 시작되면, 갑은 식탁 위에 있는 피자탑들 중 하나를 고릅니다. 그리고 고른 피자탑을 두 개의 피자탑으로 분리합니다. 이때 갑은, 분리된 두 피자탑의 높이의 곱만큼 즐거움을 느낍니다. 즉, 갑이 고른 피자탑의 높이가 A이고, 갑이 이 피자탑을 높이 B인 피자탑과 높이 C인 피자탑으로 분리했다면, 갑은 이때 B * C만큼의 즐거움을 느낍니다. 단, 높이가 1인 피자탑은 더는 분리시키지 않습니다. 갑은 계속 피자탑들을 분리해나갑니다. 이 놀이를 하다가 식탁 위에 더 이상 분리할 수 있는 피자탑이 없어진다면, 갑의 개강총회 준비 일은 끝나게 됩니다. 갑은 문득, 혼자 놀기를 통해 얼마나 재밌게 놀 수 있을지 궁금해졌습니다. 갑이 주문한 피자판의 수 N 이 주어질 때, 갑이 혼자 놀기를 통해 얻을 수 있는 즐거움의 총합의 최댓값을 구해주세요.

 

입력: 첫 번째 줄에는 피자판의 개수를 의미하는 양의 정수 N(1 ≤ N ≤ 10) 이 주어진다.

출력: 갑이 얻을 수 있는 즐거움의 총합의 최댓값을 한 줄에 출력한다.