25793 초콜릿 피라미드 (백준, python3)

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

시간 제한	메모리 제한
1초	1024MB

문제

코코는 특이하게 생긴 화이트 초콜릿과 다크 초콜릿을 무한히 많이 갖고 있다. 화이트 초콜릿은 각 모서리의 길이가 1인 사각 피라미드이고, 다크 초콜릿은 각 모서리의 길이가 1인 정사면체 모양이다. 어느 날 코코는 이 초콜릿들을 가지고 놀다가, 초콜릿을 잘 쌓으면 더 큰 사각 피라미드를 만들 수 있다는 사실을 알아냈다. 바닥면의 직사각형의 크기가 R×C인 피라미드를 쌓는 구체적인 방법은 다음과 같다.

• 먼저 바닥을 R×C개의 화이트 초콜릿으로 채운다.
• 화이트 초콜릿 사이사이를 다크 초콜릿으로 채운다.
• 다크 초콜릿 사이의 공간을 다시 화이트 초콜릿으로채운다. 여기까지 진행하면 위쪽 면은 (R - 1)×(C - 1) 크기의 평평한 직사각형이 된다.
• 윗면의 넓이가 0이 될 때까지 반복한다.

아래 그림은 2×3 피라미드의 1층을 채우는 과정을 나타낸 것이다. 1층을 채우는 데에 화이트 초콜릿은 8개, 다크 초콜릿은 7개가 필요하고, 2층까지 합하면 각각 10개, 8개가 필요하다.

코코는 아주 큰 초콜릿 피라미드를 만들어 한별이에게 선물하려고 한다. 이 때 화이트와 다크 초콜릿이 각각 몇 개씩 필요한지 계산해주자.

 

입력

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 T개의 줄 각각에는 정수 R과 C의 값이 순서대로 주어진다.

• 1 ≤ T ≤ 10⁵
• 1 ≤ R, C ≤ 10⁶

 

출력

각 테스트 케이스에 대해, 필요한 화이트 초콜릿의 개수와 다크 초콜릿의 개수를 한 줄에 순서대로 출력한다.

 

---

풀이

R과 C를 1씩 깎아가며 한 층마다 필요한 초콜릿의 수를 더해나가면 어림잡아 10¹¹회 연산이 필요합니다. 한층씩 살펴보는 과정에서 반드시 시간초과가 발생하기 때문에 R과 C의 값으로 전체 피라미드에 필요한 초콜릿의 수를 얻을 수 있는 방법을 찾아봅시다.

 

먼저 한 층에 필요한 초콜릿의 양을 계산해봅시다.

1) 가로 R, 세로 C 크기의 층에 화이트 초콜릿을 R * C개 채워 넣습니다. = RC

2a) 가로줄 사이사이에 필요한 다크 초콜릿은 (R - 1) * C개 입니다. = (R - 1)C

2b) 세로줄 사이사이에 필요한 다크 초콜릿은 R * (C - 1)개 입니다. = R(C - 1)

3) 남은 빈 공간에 필요한 화이트 초콜릿은 (R - 1) * (C - 1)개 입니다. = (R - 1)(C - 1)

그러면 한 층에 필요한 초콜릿의 양은 이렇습니다.

 

화이트 초콜릿 = 1) + 3) = RC + (R - 1)(C - 1) = RC + RC - R - C + 1 = 2RC - R - C + 1
다크 초콜릿 = 2a) + 2b) = (R - 1)C + R(C - 1) = RC - C + RC - R = 2RC - R - C

 

R과 C가 주어졌을 때 만들 수 있는 최대 층 수는 둘 중 작은 값과 같습니다. 그러면 R과 C가 1씩 줄며 위의 초콜릿 양을 계속해서 더해주어야 합니다. 편의상 R과 C를 바꾸어 C를 더 작은 값으로 바꿔놓겠습니다. 그리고 화이트 초콜릿이 다크 초콜릿보다 매 층마다 1개씩 더 필요한 것을 알 수 있습니다. 따라서 다크 초콜릿의 양을 먼저 구한 후에 전체 층 수(C)를 더하면 화이트 초콜릿의 양을 얻을 수 있습니다.

 

식을 간단히 하기 위해 R - C = k로 정하고 식을 정리하겠습니다.

화이트 초콜릿 = 다크 초콜릿 + 1
다크 초콜릿 = 2RC - R - C = 2(C + k)C - (C + k) - C = 2C² + 2kC - C - k - C = 2C² + 2(k - 1)C - k

수열의 합 공식을 이용해 정리하면 전체 피라미드에 필요한 다크 초콜릿의 양은 다음과 같이 구할 수 있습니다.

 

 

정답 코드

import sys
input = sys.stdin.readline
def solution():
    for _ in range(int(input())):
        r, c = map(int, input().split())
        if r < c: r, c = c, r
        t = (c * (c + 1) * (c * 2 + 1)) // 6
        d = (c * (c + 1)) // 2
        k = r - c
        res = t * 2 + (k - 1) * d * 2 - k * c
        print(res + c, res)
solution()