프로그래머스 숫자의 표현(lv2, python)

https://school.programmers.co.kr/learn/courses/30/lessons/12924

프로그래머스

문제 접근

주어진 수 이하의 연속된 자연수의 합으로 주어진 수를 표현할 수 있는 경우의 수를 모두 구하는 문제

 

아이디어

• n이 10,000(10^4)이하 이므로 대충 O(n^2) 이하의 시간복잡도면 풀 수 있겠다 판단함
• 이중 for문으로 완전탐색해주면 시간복잡도상 애매한데, 정답이 구해지는 경우랑 정답이 나올 수 없는경우 break를 걸어주면 충분히 가능하겠다 싶어서 구현시작

 

정답 코드

def solution(n):
    count = 0
    for i in range(1, n+1): 
        temp = 0
        for j in range(i, n+1):
            temp += j
            if temp == n:
                count += 1
                break
            elif temp > n:
                break 
        
    return count