메모이제이션 memoization

import sys
input = sys.stdin.readline
n = int(input())

for i in range(n):
    length, count = map(int, input().split())
    space = input()
    answer = 0
    memo = []
    for j in range(count):
        a, b = map(int, input().split())
        if memo.count((a, b)):
            answer += 1
        else:
            if len(space) >= 3:
                if space[a-1] == "U":
                    if b - a >= 2:
                        if space.count("m", a - 1, b) == b - a:
                            answer += 1
                            memo.append((a, b))
    print(answer)

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. - 위키백과, 우리 모두의 백과사전.

아주 좋은 개념 시간복잡도를 줄이는 방법 하나 배웠다
짱굿

레퍼런스

https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98