BOJ 20953 '고고학자 예린'

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

20953번: 고고학자 예린

 

쉬운 문제인데 평소에 머리를 워낙 안쓰다시피 하니 끙끙거린다.. 

이 문제는 처음에 이런 식으로 풀다가 시간 초과 로 인해 통과되지 않는다.

def solution(a, b):
    sum = 0
    for i in range(a + b):
        for j in range (a + b):
            for _ in range(j):
                sum += 1
    return sum

if __name__ == '__main__': 
    T = int(input())
    for _ in range(T):
        a, b = map(int, input().split())
        print(solution(a, b))

 

3중 for문을 도니까 시간이 초과해버리는 것

 

먼저 input으로 받지 말고 sys.stdin.readline 으로 받는 것으로 시작한 후 차근차근 생각해보자. (input()으로 바로 받는게 훨씬 시간이 걸리기 때문)

 

 

 

평소에 머리 안굴리면 누워서 식은 죽 먹듯이 하던 것도 갑자기 생각 안날정도로 머리가 굳어버린다..ㅠ-ㅠ

단순 for문의 실행 횟수만을 생각해보자.

for j in range(a+b):
    for _ in range(j):

의 실행 횟수를 생각해보면
0번 실행, 1번 실행, 2번 실행, ... , a + b -1 번 실행이므로

등차수열 공식 참고

(a + b - 1) * (a + b) / 2

가 됨을 알 수 있다. 

 

 

 

 

이걸

for i in range(a+b):
  for j in range(a+b):
      for _ in range(j):

하면 (a + b) x (a + b - 1) / 2 을 다시 (a + b)번 실행하므로

(a + b) x (a + b) x (a + b -1) / 2 가 된다.

이걸 코드로 실행하면

import sys

if __name__ == '__main__': 
    T = int(input())
    for _ in range(T):
        a, b = map(int, sys.stdin.readline().split())
        print((a + b)**2*(a + b -1)//2)

다음과 같이 된다. 참 쉽죠..?...ㅠ

 

 

 

 

평소에 머리 안쓰면 이런 것도 갑자기 뇌정지 온다.. (기가 막히고 코가막혀..)

많이는 아니더라도 진짜 조금씩만 시간 내서 알고리즘 풉시다..