Programmers - 숫자의 표현

SJ0000·2022년 5월 15일
0

문제 링크

A<=B 일때 A ~ B 까지의 합은 ('1 ~ B'의 합) - ('1 ~ A-1'의 합) 과 동일하다.

1~x 까지의 합을 psum[x] 에 저장하고 A~B의 합을 psum[B]-psum[A-1] 로 계산하면

A ~ B의 합을 시간복잡도 O(1) 에 구할 수 있다.

처음에는 break 처리를 하지 않고 전부 순회했는데, 이 때 시간초과가 발생했다.
더 이상 확인해도 의미가 없는 시점에 break를 추가하였더니 시간초과가 사라지고 통과되었다.

def solution(n):
    MAXN = 10000
    psum = [0 for _ in range(MAXN+1)]
    psum[0] = 0
    for i in range(1, MAXN+1):
        psum[i] = psum[i-1]+i

    answer = 0
    for st in range(0, n+1):
        for ed in range(st+1, n+1):
            current = psum[ed]-psum[st]
            if current > n:
                break

            if current == n:
                # print(st, ed)
                answer += 1
                break

    return answer    
profile
잘하고싶은사람

0개의 댓글