[구현/수학] 백준 25793 초콜릿 피라미드 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

25793번: 초콜릿 피라미드

 

 

2. 문제 풀이

 화이트 초콜릿과 다크 초콜릿을 번갈아가며 층층이 피라미드를 쌓는 문제입니다.

 

 

3. 코드

import sys
input = sys.stdin.readline

"""
    2*3 = 8, 7
    1*2 = 2, 1
"""

# 입력
t = int(input())
for i in range(t):
    r, c = map(int, input().split())
    white = 0
    floor = 0
    white = r*c

    # 윗면의 넓이가 0이 될 때까지 반복
    while r * c != 0:
        floor += 1
        r -= 1
        c -= 1
        white += r*c*2
    print(white, white - floor)

 문제에서 제시한대로 풀면 되지만, 시간제한이 빡빡한 편입니다.

 위와 같이 반복문으로 풀 경우에는 시간 초과가 납니다.

 

#include <stdio.h>

int main()
{
    int t;
    scanf("%d", &t);
    for(int i=0; i<t; i++){
        int r;
        int c;
        scanf("%d %d", &r, &c);
        int white = r*c;
        int f = 0;
        
        while(r*c != 0){
            f += 1;
            r -= 1;
            c -= 1;
            white += r*c*2;
        }
        printf("%d %d\n", white, white-f);
    }
}

이는 파이썬 언어가 느려서도 아닙니다. 그저 단순 구현으로 풀면 안됩니다.

 

import sys
input = sys.stdin.readline

# 입력
t = int(input())
for i in range(t):
    r, c = map(int, input().split())
    white = r*c

    n = min(r, c) - 1
    a = max(r, c) - n - 1
    white += 2*(((n * (n+1) * (2*n + 1))//6) + ((a * n * (n+1))//2))
    print(white, white-n-1)

 반복문 없이, 초콜릿이 늘어나는 규칙을 찾아야 합니다.

 저도 이 문제의 등차수열 합 공식을 찾기 위해, 수학 사이트를 많이 뒤졌습니다..