[프로그래머스/Level2] 숫자의 표현(Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12924

문제 접근

해당 문제는 처음에 단순하게 1~n까지 더해오면서 맡으면 count += 1, 더해온게 더 커지면 종료라고 생각했다.

문득 든 생각이 있다.

굳이 n까지 돌 필요가 있을까?

100의 경우, 100의 절반인 50까지 와서도 100에 도달하지 못했다면 그 뒤로는 볼 필요가 없는 것이다.(50+51은 이미 100을 넘어섰기 때문)

하지만, 101과 같이 50+51=101인 경우가 있기 때문에 절반 + 1까지 돌도록 로직을 구성했다.

소스 코드

def solution(n: int) -> int:
    if n < 3:
        return 1
    
    answer = 1
    
    for i in range(1, n // 2 + 2):
        sum_val = 0
        for j in range(i, n // 2 + 2):
            sum_val += j
            if sum_val == n:
                answer += 1
            
            if sum_val > n:
                break
    
    return answer