백준 20953번 - 고고학자 예린

출처 : 20953번: 고고학자 예린 (acmicpc.net)

20953번: 고고학자 예린

---

고고학자 예린 성공 출처 분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초

1024 MB

142

56

49

47.573%

문제

예린은 고고학자이다. 예린은 강원대학교 백록관 지하에서 고인돌이 발견되었다는 소식을 듣고 누구보다 빠르게 백록관에 도착하였다. 고인돌을 본 순간 예린은 놀라 자빠질 수밖에 없었다. 고인돌에 의미를 알 수 없는 문자들이 가득 새겨져 있었기 때문이다. 예린은 이 문자들을 누구보다 빠르게 그리고 남들과는 다르게 해석하기로 결심하였다.

열심히 연구한 결과 예린은 이 문자들이 어셈블리 언어의 함수 코드를 의미함을 발견하였다. 아래 코드는 고인돌의 어셈블리 언어 코드와 동일한 기능을 하는 C 코드이다.

int dolmen(int a, int b) {
    int sum, i, j, k;
    sum = 0;
    for (i = 0; i < a + b; i++) {
        for (j = 0; j < a + b; j++) {
            for (k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

정수 a와 b가 주어졌을 때, 함수 dolmen(a, b)의 실행 결과를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

이후 T개의 줄에 걸쳐 정수 a와 b가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대한 답을 한 줄에 하나씩 출력한다.

제한

• 1 ≤ T ≤ 100,000
• 1 ≤ a, b ≤ 777

예제 입력 1 복사

3

1 2

2 3

3 4

예제 출력 1 복사

9

50

147

---

[ 문제 설명 ]

 

주어진 코드 블록대로 문제를 실행하게 되면 시간 초과가 나온다. 즉, 저 3중 for문 시간복 잔도 n**3을 어떻게 줄일 거냐가 관건.

 

그림으로 설명하겠다.

 

그림 1 - 고고학자 예린 설명

---

[ 코드 ]

 

import sys


def dolmen(a, b):
    sum = 0
    sum = sum + ((a + b) ** 2 * (a + b - 1)) // 2

    return sum


TestCase = int(sys.stdin.readline())
for q in range(TestCase):
    a, b = map(int, sys.stdin.readline().split())
    res = dolmen(a, b)
    print(res)

 

---

후기

 

약간 수학 푸는 느낌이든 문제였다.