프로그래머스 숫자의 표현 level 2 PYTHON

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

 

이중 for문을 사용하여 문제를 해결할수있다고 생각했다.

하지만 시간 초과떄문에 문제를 해결할수 없었다. 시간을 줄일려면 어떻게 해야할까라는 부분에 대해서 고민을했다.

def solution(n):
    count = 1
    for i in range(1,n//2+1):
        answer = 0
        while answer <= n:
            answer += i
            if answer == n:
                count += 1
                break
            i+=1
    return count

for문의 조건을 n//2 +1 로 바꾸어주면 어차피 등차수열의 공식떄문에 절반만 계산하여도 정답을 구할수있다.

ex) 15라면 8까지만 계산하면 모든 값들을 구할수있다. 15의 경우 count를 1로 시작하게 됨으로써 15자체를 포함하게 되는것이다.