숫자의 표현

문제

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

 

· 1 + 2 + 3 + 4 + 5 = 15 

· 4 + 5 + 6 = 15 

· 7 + 8 = 15

· 15 

 

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

 

제한사항

· n은 10,000이하의 자연수입니다.

 

입출력 예

n	result
15	4

---

풀이

1. Me

1) 1차 시도

def solution(n):
    list_n = list(range(1,n+1))
    # print(list_n)
    answer = 1   # 자기 자신 
    for i in range(len(list_n)):
        start_idx = i
        for j in range(i+1, len(list_n)):
            if sum(range(list_n[i], list_n[j])) == n:
                # print(i, j)
                answer += 1
    # print(answer)
    return answer

연속된 수를 구하기 위해, 입력받은 수에 해당하는 범위까지의 수를 담은 리스트를 만들고, 해당 리스트를 이중 탐색하며 두 개의 인덱스를 통해 연속된 수의 덧셈을 구현하였다.. 정확성 테스트는 모두 통과하였지만, 효율성에서 다 틀렸다.. 주륵 ..

 

2) 2차 시도

def solution(n):
    list_n = list(range(1, (n+1) // 2 + 1))
    answer = 1   # 자기 자신 
    for i in range(len(list_n)):
        start_idx = i   # 0 ~ 7
        for j in range(i+1, len(list_n)):   # 1 ~ 7
            if sum(range(list_n[i], list_n[j] + 1)) == n:
                answer += 1
    return answer

길이를 절반으로 줄여도 여전히 효율성 테스트에서 통과하지 못한다 ..

 

3) 3차 시도

def solution(n):
    list_n = list(range(1, (n+1) // 2 + 1))
    print(list_n)
    answer = 1   # 자기 자신 
    for i in range(len(list_n)):
        start_idx = i   # 0 ~ 7
        for j in range(i+1, len(list_n)):   # 1 ~ 7
            if sum(range(list_n[i], list_n[j] + 1)) == n:
                # print(i, j)
                answer += 1
                break
            elif sum(range(list_n[i], list_n[j] + 1)) > n:
                break
    # print(answer)
    return answer

길이를 절반으로 줄이고, break문을 사용하여 최소한으로 반복하도록 구현하였다.. 그랬더니 통과 ! 

 

2. Others

def expressions(num):
    answer = 0
    for i in range(1, num + 1):
        s = 0
        while s < num:
            s += i
            i += 1
        if s == num:
            answer += 1

    return answer

이렇게 작성하면 한 번만 탐색하고 마무리 할 수 있는건가 .. ? 시간복잡도가 어떻게 되는거지 잘 모르겠다.

def expressions(num):
    return len([i  for i in range(1,num+1,2) if num % i is 0])

등차수열 합의 공식을 이용했다고 한다.. 자기보다 작은 홀수로 나누어 떨어지는 값의 개수 = 문제의 답